Une première idée :
Peser la moitié des pièces (2 pièces) le poids total de ces deux pièces disons A,B
indique la répartition des deux pièces fausses :
20g (0) : les deux pièces fausses sont dans le lot restant CDE
19g (1) : une est dans AB, l'autre dans CDE
18g (2) : les deux pièces fausses sont AB, c'est fini
Dans deux des cas il faut poursuivre.
D'autres tentatives échouent et nécessitent dans le pire cas 4 pesées.
Mais alors ? impossible en 3 pesées ???
Si, il y a une astuce : il faut répartir les pesées en lots de pièces non disjoints
Par exemple les trois pesées ABC, BCD, CE.
Si on recense tous les cas de figure, on obtient :
pièces résultat des
fausses pesées
ABC BCD CE
AB... 2 1 0
A.C.. 2 1 1
A..D. 1 1 0
A...E 1 0 1
.BC.. 2 2 1
.B.D. 1 2 0
.B..E 1 1 1
..CD. 1 2 1
..C.E 1 1 2
...DE 0 1 1
Comme les 10 résultats sur ces 3 pesées sont différents, ils discriminent bien les 10 répartitions de pièces.
Attention : Je sais qu'il y a deux pièces fausses !
Sinon, pour trouver un nombre inconnu de pièces fausses dans mon lot de 5,
il me faut les 5 pesées.
Le cas de 3 pièces fausses dans mon lot est identique au cas de 2 pièces bonnes.
En remplaçant formellement 'bonne' par 'fausse' et vice versa, la méthode est exactement la même.
Le cas de 1 ou 4 pièces fausses est élémentaire, même des pesées disjointes le résolvent, en 3 pesées.
| Pour trouver p pièces fausses parmi 5 (p donné)
il suffit de 3 pesées quel que soit p |
Bien sûr p=0 et p=5 ne nécessitent aucune pesée, et si on a de la chance, moins de 3 pesées suffisent. Le problème est dans le pire cas.
f(n,0)=0 f(n,n)=0 f(n,p)=f(n, n-p)
Notre stratégie de pesées disjointes est donc la suivante :
Si je pèse k pièces de mon lot de n, j'obtiens p' pièces fausses dans ce lot de k.
Il reste donc p-p' pièces fausses dans le lot de n-k (sans avoir besoin de le peser).
La stratègie consiste alors à recommencer pour chacun des deux lots de k et n-k pièces.
Et donc :
f(n,p) = f(k,p') + f(n-k,p-p') + 1
Les f(k,p') nécessaires pour trouver les p' pièces du lot de k, plus les f(n-k,p-p') pesées nécessaires pour trouver les p-p' pièces du lot de n-k, plus la pesée initiale du lot de k.
Maintenant, pour élaborer ma stratégie, je ne connais pas à priori la valeur de p'
avant d'avoir effectivement pesé mes k pièces, donc avant d'avoir choisi k.
Ma stratégie va être de choisir k pour avoir, au pire cas des valeurs de p', le f(n,p) minimal,
et donc
f(n,p) = Min/k ( Max/p' ( f(k,p') + f(n-k,p-p') + 1 ) )
On obtient ainsi de proche en proche, à partir de f(1,p)=0 pour tout p,
les valeurs de f(n,p) et les valeurs de k correspondantes.
La valeur de k étant celle pour laquelle Max/p' ( f(k,p') + f(n-k,p-p') + 1 ) est minimale.
Il y a généralement plusieurs valeurs de k donnant le même minimum.
Remarquons que peser le tas de k ou le tas de n-k est équivalent. On peut donc se contenter de 1≤k≤n/2.
Le tableau suivant donne les valeurs de k la plus grande ≤n/2 et la valeur de f :
| n\p | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | _ (f=0) | _ (f=0) | ||||
| 2 | _ (f=0) | 1 (f=1) | _ (f=0) | |||
| 3 | _ (f=0) | 1 (f=2) | 1 (f=2) | _ (f=0) | ||
| 4 | _ (f=0) | 2 (f=2) | 2 (f=3) | 2 (f=2) | _ (f=0) | |
| 5 | _ (f=0) | 2 (f=3) | 2 (f=4) | 2 (f=4) | 2 (f=3) | _ (f=0) |
| ... | ||||||
On voit que cette stratégie n'est pas optimale, elle donne f(5,2)=4.
C'est bien ce que nous avions obtenu dans la première partie :
il est nécessaire d'effectuer des pesées de lots non disjoints.
La méthode utilisée dans la première partie, pour chercher ces lots
en examinant les résultats de pesées pour toutes les combinaisons de pièces,
est bien entendu impraticable pour les grandes valeurs de n.
Avec 10 pièces fausses parmi 100 il y a C10010 = 17310309456440 combinaisons
possibles.
La méthode des pesées disjointes ne nécessite pas "trop" de travail :
il faut effectuer de l'ordre de n4 opérations pour obtenir toutes les valeurs de f jusqu'à f(n,n/2),
les nombres de combinaisons croissent bien plus vite !
Un petit programme (ici en Java) donne les valeurs jusqu'à f(100,10) en quelques secondes.
On obtient ainsi f(100,10)=42.
En fait notre méthode n'étant pas optimale on a f(100,10) ≤ 42
Le tableau donne le plus grand k ≤ n/2, et entre parenthèse la valeur de f(n,p).
En cliquant sur une valeur, on a la liste complète des valeurs de k donnant le Min/k.
On peut relancer les calculs avec des valeurs de n et p max plus grandes.
Pour avoir encore un temps de calcul raisonnable, n < 200 et p ≤ 20.
On peut ainsi se promener de case en case sur le tableau pour détailler la stratégie des 42 pesées
au fur et à mesure :
Peser un lot de 48 pièces,
puis du lot de 48 pièces (s'il y en a des fausses)
peser 16 ou 24 pièces selon le nombre de pièces fausses.
Dans le lot restant de 52 pièces, peser 24 ou 26 pièces (s'il y en a des fausses, selon leur nombre)
etc...
Comme il y a d'autres valeurs de k que celle indiquée directement dans le tableau, il y a plus simple, en examinant les listes complètes des valeurs de k on obtient par exemple :
| Trouver 10 pièces fausses dans un lot de 100 |
| Pesées à effectuer selon la taille des lots :
Lot de 100 pièces : peser 36 pièces, reste 64
|
Ou bien sûr le complément. On peut peser 36 ou 64 pièces au départ, on obtient la même information : le nombre de pièces dans le lot de 36 et le nombre de pièces dans le lot de 64.
On notera la prédominance de lots de 2i pièces. Ceci n'est pas une coïncidence...