Retrouver Une Boule Parmi 12 En Un Minimum De Pesées

Problème

On considère 12 boules visuellement identiques, telles que 11 d'entre elles ont le même poids et une a un poids différents. On dispose d'une balance Roberval. Quel est le nombre minimum de pesées permettant d'identifier la boule de poids différent ?

Solutions

Borne évidente

La première chose à remarquer est qu'une pesée a 3 issues possibles :

• la balance penche à gauche (G)
• la balance penche à droite (D)
• la balance ne penche pas (N)

Ainsi, une pesée fournit un trit d'information.

Deux pesées permettront de distinguer 3·3 = 3² = 9 configurations. Trois pesées permettront de distinguer 3³ = 27 configurations.

Le problème demande de distinguer parmi 12 configurations (si on numérote les boules, il s'agit de déterminer quel est le numéro de la boule de poids différent)

Ainsi, il faut au moins 3 pesées pour espérer identifier la boule le poids différent dans tous les cas.

Une première solution

TODO

Une solution sans arbre de décision

Le type de raisonnement précédent consistant à trouver un arbre de décision par essai/erreur a l'avantage de permettre à tout le monde de chercher, et à finir par trouver une solution si elle existe (et son on envisage toutes les possibilités).

TODO

Ainsi, on remarque que non seulement il est possible de déterminer la boule de poids différent, mais aussi de déterminer si elle est plus lourde ou plus légère que les autres.

Une solution par arbre de décision qui permette

Convaincu·es par la méthode précédente, on peut essayer d'améliorer la première méthode pour pouvoir aussi déterminer si la boule de poids différent est plus lourde ou plus légère que les autres à l'aide d'un arbre de décision.

TODO

13 boules ?

On remarque que 2·13 = 26 < 27 = 3³ de sorte que la borne informationnelle ne permet par *a priori* d'éliminer la possibilité de trouver une boule de poids différent parmi 13 et de déterminer si cette boule est plus lourde ou plus légère que les autres.

Tout d'abord, il est possible de trouver la boule de poids différent.

TODO

Par contre, il n'est pas possible de déterminer si la boule de poids différent est plus lourde ou plus légère que les autres.

TODO