FOIRE AUX QUESTIONS DE fr.sci.maths                 CHAPITRE IV: ENIGMES

 


IV-1. Pièces et balance

SUJET PRECEDENT - INDEX - SUJET SUIVANT

Traduction de logic/weighing/balance des archives de rec.puzzles http://alabanza.com/kabacoff/Inter-Links/puzzles.html; 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. Associez donc chaque pièce à une chaîne de P caractères. 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. 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 faites une recurrence sur le groupe contenant la pièce lourde.