next up previous contents
Next: Effectuez pesées comme suit: Up: Pièces et balance. Previous: Énoncé.   Contents

Solution.

Martin Gardner1.4a donné une jolie solution à ce problème. Supposez que vous avez le droit à $P$ pesées. écrivez les $3^P$ chaînes possibles de longueur $P$ ayant pour caractères ``$0$'', ``$1$'' et ``$2$''. éliminez les 3 chaînes comportant uniquement un caractère répété $P$ fois.

Pour chaque chaîne, trouvez le premier caractère différent du caractère le précédant. Considérez ce couple de caractères. Si ce couple n'est pas 01, 12 ou 20, éliminez cette chaîne. En d'autres termes, seules les chaînes de la forme $0*01.*$, $1*12.*$ ou $2*20.*$ (expressions rationnelles) sont acceptées.

Il doit vous rester $(3^P-3)/2$ chaînes. C'est le nombre de pièces que vous pouvez contrôler en $P$ pesées. Associez donc chaque pièce à une chaîne de P caractères.


Subsections

Faq de fr.sci.maths 2003-12-14