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 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 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. 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 pièces. Avec P
pesées, il ne peut y avoir que
combinaisons d'équilibre, plateau de gauche plus lourd et
plateau de droite plus lourd.