Traduction de logic/weighing/balance des archives de rec.puzzles

Traduction de logic/weighing/balance des archives de rec.puzzles
<http://rec-puzzles.org/>

Problème
--------
On vous donne 12 pièces qui paraissent identiques, dont l'une est
contrefaite et a un poids légèrement différent des autres (vous ne
savez pas si la pièce est plus lourde ou plus légère). On vous donne
une balance de Roberval, qui vous permet de mettre le même nombre de
pièces de chaque côté et d'observer quel côté (s'il y en a un) est
plus lourd. Comment identifier la pièce contrefaite et déterminer si
elle est plus lourde ou plus légère, en 3 pesées?

Solution
--------
Martin Gardner a 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.

Effectuez P pesées comme suit:

    Pour la pesée I, mettez d'un côté toutes les pièces ayant un 0
    dans la chaîne en position I, et mettez de l'autre côté toutes
    les pièces ayant un 2 dans la chaîne en position I.

    Si le côté avec les 0 en position I est plus lourd, écrivez un 0.
    Si c'est l'autre côté qui est plus lourd, écrivez un 2. Sinon,
    écrivez un 1.

Après P pesées, vous avez écrit une chaîne de P caractères. Si votre
chaîne correspond à une des pièces, alors c'est cette pièce qui est
contrefaite, et elle est plus lourde. Sinon, changez chaque 2 en 0
et chaque 0 en 2 dans votre chaîne. Votre chaîne correspondra alors
à l'une des pièces, et cette pièce est plus légère que les autres.

Notez que si vous devez seulement identifier la pièce contrefaite,
mais pas déterminer si elle est plus lourde ou plus légère, vous
pouvez contrôler (3^P-3)/2+1 pièces. Étiquetez la pièce supplémentaire
par la chaîne contenant uniquement des 1, et utilisez la méthode
ci-dessus.

Notez aussi que vous pouvez contrôler (3^P-3)/2+1 pièces si vous
devez déterminer si la pièce contrefaite est plus lourde ou plus
légère, pourvu que vous ayez une pièce de référence, dont vous savez
qu'elle a le poids correct. Vous faites ceci en étiquetant la pièce
supplémentaire par la chaîne contenant uniquement des 2. Ainsi, cette
pièce est placée toujours du même côté, et ce plateau contient une
pièce de plus que l'autre. Alors, placez la pièce de référence de
l'autre côté, à chaque pesée.

Il est très facile de prouver que ceci marche, une fois que vous avez
remarqué que la méthode de construction des chaînes assure qu'à chaque
position, 1/3 des chaînes ont un 0, 1/3 ont un 1, et 1/3 ont un 2, et
que si une chaîne est dans la liste, alors celle obtenue en remplaçant
chaque 0 par un 2 et chaque 2 par un 0 n'y est pas.

Si vous savez déjà que la pièce contrefaite est plus lourde (ou plus
légère), vous pouvez contrôler 3^P pièces. Avec P pesées, il ne peut
y avoir que 3^P combinaisons d'équilibre, plateau de gauche plus lourd
et plateau de droite plus lourd.

L'algorithme est dans ce cas:

Partagez les pièces en 3 groupes de même taille... A, B et C. Pesez
A avec B. Si un plateau tombe, il contient la pièce lourde, sinon
cette pièce est dans le groupe C. Si la taille de votre groupe est 1,
vous avez trouvé la pièce, sinon récursivez sur le groupe contenant
la pièce lourde.