Mathieu Seurat a écrit :
"Philippe 92" <nospam@free.invalid> a écrit dans le message news:
mn.babf7d85cb14b608.22155@free.fr...
Une borne inférieure est donné par la "quantité d'information"
Il y a C(100,10) = 17 310 309 456 440 répartitions possibles des pièces.
Si une pesée donne a[i] résultats possibles, la quantité
d'information obtenue est au mieux le produit des a[i] (moins si les
informations obtenues sont redondantes).
Il est donc nécessaire que ce produit soit au moins égal au nombre de
répartitions. Soit prod(a[i]) >= C(100,10)
Cette possibilité est indépendante d'un calcul par pesées. C'est comme si
vous disiez : devant peser un kilogrammes, je doit peser mille fois un
gramme.
Mais non voyons.
D'abord il ne s'agit pas de peser 1 kilogramme mais de peser une
quantité inconnue.
Ensuite une seule pesée donne directement le poids cherché.
Enfin là il ne s'agit pas de peser *un* objet, mais d'en peser 100 !
(les 100 pièces, dont on veut déterminer le poids de chacune).
Et bien entendu pas en 100 pesées !
Ma remarque sur la quantité d'information obtenue par les pesées
*choisies* qui doit être supérieure ou égale au nombre de cas
possibles (les C(100,10) répartitions possibles) est valable
"universellement".
Mon algorithme précédent arrivait à 60 pesées maximum et 6 pesées
minimum. Ce qui contredit votre hypothèse.
Ca ne contredit rien du tout :
Malheureusement cette borne est si grossière qu'elle n'aboutit pas
à grand chose.
La seule chose que ça "contredit" est : cette remarque n'aboutit à
rien de bien utile.
Sans "astuce" la détermination de 2[*] pièces fausses parmi 5 en 3
pesées seulement n'est déja pas évidente, et nécessite de peser
certaines pièces plusieurs fois.
Moi même je me suis fait pièger (une confusion sur le type de
balance peut-être ?)
Sur cinq pièces, il suffit pourtant de trois pesées au maximum pour
determiner n'importe quelle quantité de pièces fausses parmi les pièces
vraies.
Hélas, c'est faux.
Après examen attentif, avec 2 pièces fausses parmi 5 il faut 4 pesées.
Le problème de trouver 10 pièces fausses parmi 100 n'est pas
facteur de trouver une pièce fausse parmi dix.
"facteur de trouver" ?? no comprendo...
Il se peut qu'une distribution hasardeuse des pesées arrivent à 60.
"distribution hasardeuse" ??? no comprendo.
Le hasard n'a rien à voir la dedans, ni "il se peut".
Il faut trouver une méthode de pesée telle que le maximum du nombre
de pesées nécessaire pour *toutes* les répartitions de pièces avec
*cette* méthode, soit la plus petite possible parmi l'ensemble de
toutes les méthodes de pesées.
Alors oui, si on choisit n'importe qelle méthode, "il se peut" que...
cette méthode soit celle qu'on cherche, ou soit mauvaise, ou...
Et puis on peut aussi "tester" la méthode en essayant les 17 millions
de millions de répartition des pièces. Comme ceci est totalement
irréaliste, on peut vouloir tester en choisissant "au hasard"
quelques répartitions. Malheureusement ceci ne prouvera rien du tout.
60 est donc inclue.
Et ben non, puisque Jacky a montré (enfin presque[**]) que 49 pesées
suffisent toujours.
nota [*] : détermination des pièces parmi 5
1 pièce fausse : assez évident
Reste trois pesées au maximum.
OK.
2 pièces fausses : pb intéressant
Je ne vois pas où est le problème. Reste aussi trois pesées au maximum.
Faux.
3 pièces fausses = 2 pièces bonnes
Donc faux aussi. 4 pesées sont nécessaires
4 pièces fausses = 1 pièce bonne
OK, 3 pesées.
Nota [**] :
Sur la méthode "préconisée" :
Peser 20 tas de 5 pièces (avec 19 pesées effectives, hein. La 20ème
est obtenue par soustraction) puis déterminer les pièces fausses dans
chacun des *au plus* 10 tas de 5 pièces qui s'avèrent contenir des
pièces fausses. ce qui donne 10*3 = 30 pesées supplémentaires.
Là où ça coince est justement le 10*3 !
Puisqu'il faut 4 pesées pour trouver 2 ou 3 pièces fausses parmi 5.
Seuls les cas de 1 et 4 pièces fausses sont résolus avec 3 pesées
seulement.
Il faut donc examiner les cas où il y aurait des tas de 5 pièces
avec 2 ou 3 pièces fausses dedans, tas qui nécessitent 4 pesées.
Mais alors il y a moins de tas en tout. Et c'est bien sûr pas 10*4
non plus.
En fait le nombre total maximum de pesées additionnelles pour toutes
les partitions des 10 pièces fausses en tas d'au plus 5 pièces fausses
est bien pour la répartition "1 pièce fausse dans chacun des 10 tas".
Soit bien 10*3.
Encore fallait il le prouver (examiner les 30 partitions).
Mais d'autres méthodes sont possibles (et moins faciles à tester).
Mais là c'est une autre histoire :
Soit f(n,p) le nombre minimal de pesées nécessaire pour trouver p
pièces fausses dans un tas de n. (on cherche f(100,10)).
Si on effectue alors une pesée de k pièces on réduit le problème à
trouver p' pièces parmi k + le problème de trouver p" parmi (n-k)
et on a donc f(n,p) = f(k,p') + f(n-k, p") + 1
bien entendu p' <= k, p" <= n - k et p' + p" = p
on opère ainsi une "descente" (puisque n et n-k tous deux < n)
qui se termine forcément.
Ce qui nous intéresse est le maximum de f(n,p) sur l'ensemble
des répartitions possibles, c'est à dire toutes les valeurs de p.
Sachant que pour chaque valeur de p, on a choisi les valeurs
successives de k pour avoir ce maximum aussi petit que possible
(k = "méthode de pesée").
On note ce max(f(p,n)) sur l'ensemble des valeurs de p, simplement
F(n).
On a bien entendu par définition f(p,n) <= F(n) quel que soit p
et F(n) = F(k) + F(n-k)
Les premières valeurs de f(n,p) sont
f(1,p) = 0 (he he) donc F(1) = 0
f(2,0) = f(2,2) = 0 (he he) et f(2,1) = 1, donc F(2) = 1
....
et par récurrence F(n) = n-1
On voit en particulier que F(5) = 4, dû au f(5,2) = f(5,3) = 4,
bien que f(5,1) = f(5,4) = 3, mais on s'en fiche : ce n'est pas le
pire cas...
Pour tout tas de moins de 10 pièces, F(n) = n-1, facile.
Pour plus de 10 pièces, les conditions du problème demandent de
trouver le max(f(n,p), 0<=p<=10) qui n'est plus n-1 du tout.
Et là intervient l'examen de toutes les répartitions de p' et p" avec
p'+ p" = p (<=10, donc parfois <= k ou à n-k).
Bref, c'est pas gagné...
--
Philippe C., mail : chephip
avec free.fr comme domaine
site :
http://chephip.free.fr/ (divertissements mathématiques)
