La fausse pièce

Dans l’épisode 18 de la saison 2 de Brooklyn Nine-Nine (l’épisode Captain Peralta), capitaine Holt donne l’énigme suivante à son équipe au début de l’épisode,… et ne donne jamais la réponse. L’énigme est plus difficile qu’elle n’y paraît.

La fausse pièce (**)

Vous avez 12 pièces identiques et une balance à 2 plateaux. Une de ces pièces et fausse, et a un poids différents des 11 autres. Vous devez déterminez quelle est la fausse pièce, et devez dire si elle est plus lourde ou plus légère que les autres. Vous n’avez le droit qu’à 3 pesées.

Ce problème est connu en anglais sous le nom de The counterfeit coin. J’ai trouvé beaucoup de solutions plus ou moins exactes sur des forums, mais aucune solution satisfaisante (sauf ici, mais j’avoue ne pas avoir compris pourquoi ça marchait). J’ai fini par trouver un excellent article sur ce sujet, écrit par (le) Freeman Dyson.

Sa solution, élégante, et expliquée ci-dessous, permet de traiter la généralisation suivante :

La fausse pièce -version 2- (**)

Vous avez maintenant 13 pièces, dont une fausse. Il faut trouver la fausse en 3 pesées (vous n’avez plus besoin de dire si la fausse pièce est plus lourde ou plus légère).

Cliquez ici pour voir la solution
Voici une solution pour 12 pièces, mais qui peut se généraliser directement à \({\frac12 (3^n – 3)}\) pièces, où \({n}\) est le nombre de pesées.

On numérote les pièces de 1 à 12, et on donne 1 étiquette à chaque pièce. Cette étiquette est le numéro en base 3 de la pièce (donc 3 chiffres dans l’ensemble \({\{0, 1, 2\}}\)). On donne ensuite à chaque pièce une 2ème étiquette, qui est similaire à la 1ère, mais dans laquelle on a remplacé les 0 par des 2, les 2 par des 0, et sans modifier les 1. On a ainsi placé 24 étiquettes différentes, qui sont toutes les combinaisons de 3 chiffres dans \({\{0, 1, 2\}^3}\), sauf les combinaisons 000, 111 et 222.

Enfin, on colorie chaque étiquette en rouge si le premier changement de chiffres dans la séquence est 01, 12, ou 20, et en bleu sinon. Cela permet d’avoir, à chaque position \({i}\) des étiquettes rouges, exactement 4 pièces avec un 0, 4 pièces avec un 1, et 4 pièces avec un 2. Comme nous le verrons, à la fin des pesées, il faudra regarder les étiquettes rouges dans l’hypothèse que la fausse pièce est plus lourde, et les étiquettes bleues sinon.

On obtient les étiquettes suivante (les nombres en gras sont la représentation ternaire de la pièce).

Pièce Etiquette rouge Etiquette bleue
1 001 221
2 220 002
3 010 212
4 011 211
5 012 210
6 202 020
7 201 021
8 200 022
9 122 100
10 121 101
11 120 102
12 112 110

Nous effectuons maintenant nos pesées de la manière suivante. Pour la i-ème pesée, nous prenons les 4 pièces dont l’étiquette rouge à un 2 en i-ème position, et les mettons sur le plateau de droite, et les 4 pièces dont l’étiquette rouge a un 0 en i-ème position, et les mettons sur le plateau de gauche.

  • Si la balance penche à droite, soit la fausse pièce est à droite et est lourde. Dans ce cas, elle a un 2 en i-ème position sur son étiquette rouge. Soit la fausse pièce est à gauche et est légère. Elle a alors un 0 en i-ème position sur son étiquette rouge, donc un 2 en i-ème position sur son étiquette bleue. Dans tous les cas, la fausse pièce a un 2 sur l’une de ses étiquettes.
  • Si la balance penche à gauche, on montre de la même manière que la fausse pièce a un 0 sur l’une de ses étiquettes.
  • Si la balance est stable, alors la fausse pièce n’a pas été pesée. Elle a donc un 1 en i-ème position sur ses 2 étiquettes.

Ainsi, pour chaque pesée, on marque un 2 si la balance penche à droite, un 0 si la balance penche à gauche et un 1 si la balance est stable. Le raisonnement précédent montre que le chiffre marqué coïncide toujours avec le chiffre correspondant à l’une des deux étiquettes de la fausse pièce. On a aussi montré que c’est le chiffre de l’étiquette rouge si la fausse pièce est lourde, et le chiffre de l’étiquette bleue si la fausse pièce est légère.

Au final, à la fin des 3 pesées, on a écrit le numéro d’une des étiquettes de la fausse pièce. De plus, cette pièce est lourde si on a écrit le chiffre de son étiquette rouge, et légère sinon.

Pour le deuxième problème, on rajoute la 13ème pièce avec les étiquettes 111 et 111 (elle ne sera donc jamais pesée), et le même raisonnement marche encore. Si la balance est stable pour les 3 pesées, alors c’est la 13ème pièce qui est fausse, mais on ne sait pas si elle est plus légère ou plus lourde.

Évidemment, si on sait que la fausse pièce est plus lourde, on peut la repérer au milieu de 27 pièces avec 3 pesées (pourquoi ?).

Lien pour marque-pages : Permaliens.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *