next up previous contents
Next: L'algorithme est dans ce Up: Solution. Previous: Solution.   Contents

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. 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.


next up previous contents
Next: L'algorithme est dans ce Up: Solution. Previous: Solution.   Contents
Faq de fr.sci.maths 2003-12-14