Les 12 billes et la balance

Il y a pour cette énigme 12 billes devant vous, qui ont toute le même poids sauf une qui est plus lourde ou plus légère que les autres.

Vous disposez d'une balance à plateaux et vous avez droit d'effectuer 3 pesées.

Comment trouver la bille viciée et déterminer si elle est plus lourde ou plus légère que les autres en seulement 3 pesées ?

Saurez-vous trouvez une manière "élégante" de résoudre cette énigme ?

Pour cette énigme, il y a 2 méthodes. Une méthode avec un algorithme relativement compliqué, et une autre plus élégante.
Démarrons par la plus compliquée.

Il faut commencer en divisant les billes en 3 groupes de 4 billes. On place un groupe sur chaque plateau de la balance, et on laisse le 3ème groupe de côté.

On a alors 2 possibilités : la balance est à l'équilibre, ou la balance n'est pas équilibrée

Cas n°1 : la balance est à l'équilibre

C'est le cas le plus facile, on sait alors que la bille que l'on cherche est une des 4 billes que l'on a mises de côté.
On prend 3 de ces 4 billes plus 1 bille qui faisait partie des 8 billes que l'on a déjà pesées. On sait que cette bille a le même poids que les autres.
On place alors 2 billes de chaque côté. Un des plateau de la balance se retrouve avec 2 des 4 billes mises à part pour la première pesée, l'autre plateau se retrouve avec 1 de ces billes mises à part et 1 bille normale.
Là encore, il y a 2 possibilités suivant que la balance est à l'équilibre ou pas.

Cas n°1.a : la balance est à l'équilibre

Les 4 billes sur la balance ont le même poids, c'est donc la dernière bille que l'on a mise de côté qui a un poids différent. Pour savoir si elle est plus lourde ou plus légère, il reste à faire une troisième pesée avec une autre bille et voir de quel côté penche la balance.

Cas n°1.b : la balance n'est pas à l'équilibre

Supposons que la balance penche du côté des 2 billes possiblement viciées (le raisonnement est totalement symétrique si la balance penche de l'autre côté).
Alors, la balance peut pencher pour 2 raisons différentes : soit l'une de ces 2 billes est plus lourde que les autres, soit la bille possiblement viciée qui se trouve sur l'autre plateau est plus légère.
On va prendre les 2 billes qui sont du côté où la balance penche, et on en place une de chaque côté pour la dernière pesée.

Cas n°1.b.1 : la balance est à l'équilibre

Les 2 billes sur les plateaux sont normales. C'est la bille qui était de l'autre côté pour la deuxième pesée qui est viciée, et on sait qu'elle est plus légère.

Cas n°1.b.2 : la balance n'est pas à l'équilibre

La bille viciée est parmi ces 2 billes. Grâce à la deuxième pesée, on en déduit que la bille viciée est plus lourde que les autres et que c'est donc la bille du côté où penche la balance.

Cas n°2 : la balance n'est pas équilibrée

La bille viciée se trouve parmi ces 8 billes. Appelons groupe A les 4 billes qui sont du côté où penche la balance et groupe B les 4 de l'autre côté et groupe C les 4 dernières qui ont été mises à part.
On peut en déduire que si la bille viciée est plus lourde, elle est dans le groupe A. Si elle est plus légère, elle est dans le groupe B. Le groupe C ne contient que des billes normales.

Pour la deuxième pesée, on va placer d'un côté de la balance 2 billes du groupe A et 1 bille du groupe B. De l'autre côté, on met 2 billes du groupe A et 1 bille du groupe C. On laisse donc 3 billes du groupe B de côté.

Cas n°2.a : la balance est équilibrée

Les billes sur la balance sont normales. La bille viciée est parmi les 3 billes du groupe C laissées de côté et on sait maintenant qu'elle est plus légère.
On prend 2 billes parmi ces 3 que l'on place sur chaque plateau pour la dernière pesée, on laisse la 3ème de côté.

Cas n°2.a.1 : la balance est équilibrée

C'est la bille laissée de côté qui est viciée, elle est plus légère que les autres.

Cas n°2.a.2 : la balance n'est pas à l'équilibre

C'est la bille qui est du côté où la balance ne penche pas qui est viciée. Elle est plus légère que les autres.

Cas n°2.b : la balance n'est pas à l'équilibre

Cas n°2.b.1 : la balance penche du côté où se trouve les 2 billes du groupe A et la bille du groupe B

La bille viciée se trouve parmi les 2 billes du groupe A du côté où penche la balance (cela ne peut pas être la bille du groupe B car sinon elle serait plus légère, et cela ne peut pas être 1 des 2 billes du groupe A qui sont sur l'autre plateau car elles seraient plus lourde et ferait pencher la balance de l'autre côté).

Il ne reste plus qu'à placer chacune de ces 2 billes sur un plateau pour la 3ème pesée et voir de quel côté la balance penche : on aura trouvé la bille viciée (qui est plus lourde que les autres).

Cas n°2.b.2 : la balance penche du côté où se trouve les 2 billes du groupe A et la bille normale du groupe C

La bille viciée est donc soit 1 des 2 billes du groupe A du côté où penche la balance, soit la bille du groupe B qui est de l'autre côté (la bille viciée ne peut pas être 1 des 2 autres billes du groupe A car sinon elle aurait fait pencher la balance de l'autre côté).

Pour la 3ème pesée, on place 1 des 2 billes du groupe A de chaque côté de la balance, et on laisse la bille du groupe C de côté. Si la balance est à l'équilibre, c'est la bille du groupe C qui est plus légère, sinon, c'est la bille qui est du côté où penche la balance qui est plus lourde.

On a donc un algorithme qui permet de retrouver la bille viciée et de savoir si elle est plus légère ou plus lourde que les autres.
CQFD !
Bravo à ceux qui ont suivi le raisonnement jusqu'au bout (et encore plus bravo pour ceux qui ont trouvé la solution tous seuls) !





La seconde méthode est plus simple car les 3 pesées sont tout le temps les mêmes, quels que soient les résultats des pesées précédentes.
Numérotons les billes de 1 à 12. Les pesées à réaliser sont les suivantes :

5 7 9 11 --- 6 8 10 12

3 4 6 11 --- 2 5 7 12

2 4 7 8 --- 1 5 10 11

Ensuite, on associe le nombre 9 à la première pesée, 3 à la deuxième et 1 à la dernière.
Si pour la première pesée, la balance penche à gauche, on compte +9. Si elle penche à droite, on compte -9. Si elle est équilibrée, 0.
De même pour la deuxième pesée avec 3 : +3 si la balance penche à gauche, -3 si c'est à droite, et 0 sinon.
Idem pour la dernière pesée avec 1 : +1, -1 ou 0.

On additionne alors les 3 nombres obtenus : la valeur absolue nous donne le numéro de la bille viciée ! (pour savoir si elle est plus légère ou plus lourde, il suffit de regarder le résultat d'une pesée ou la bille viciée se trouvait)

Exemple :
Supposons que la bille n°8 soit plus légère.
On aurait ainsi les résultats suivants :
pour la première pesée, la balance penche à gauche: +9
pour la deuxième pesée, la balance est à l'équilibre : 0
pour la troisième pesée, la balance penche à droite : -1
On obtient donc : 9 + 0 - 1 = 8
C'est la bille n°8 et elle est plus légère (car la balance penchait à gauche pour la première pesée).

Cette méthode fait intervenir l'écriture en base 3 des nombres de 1 à 12 (9=3^3, 3=3^1, 1=3^0), en remplaçant les 2 par des -1 pour arriver à la valeur absolue du numéro de la bille viciée. On peut remarquer qu'avec cette méthode, on pourrait même avoir 13 billes à la base (car on peut différencier en 3 pesées 3^3 = 27 combinaisons différentes, et donc 13 billes au total qui peuvent plus légère ou plus lourdes : 13x2 = 26)