Problème de pesée

En mathématiques récréatives, les problèmes de pesée sont des casse-tête logiques consistant à identifier, en un nombre minimal de pesées sur une balance à deux plateaux, une fausse pièce de poids différent parmi des pièces en apparence identiques.

Balance Roberval.

Les solutions aux diverses variantes les plus courantes de ce problème sont indiquées dans le tableau suivant .

On sait que ...	But	Nombre maximum de pièces pour $n$ pesées	Nombre de pesées nécessaires pour c pièces
la fausse pièce est plus légère (ou plus lourde) que les autres	Identifier la pièce	$3^{n}$	$\lceil \log _{3}(c)\rceil$ (2 pesées pour 9 pièces par exemple)
la fausse pièce a un poids différent	Identifier la pièce	${\tfrac {1}{2}}(3^{n}-1)$	$\lceil \log _{3}(2c+1)\rceil$ (3 pesées pour 13 pièces par exemple)
il y a une fausse pièce de poids différent, ou que toutes les pièces sont identiques	Déterminer si une pièce différente existe et si elle est plus légère ou plus lourde.	${\tfrac {1}{2}}(3^{n}-3)$	$\lceil \log _{3}(2c+3)\rceil$ (3 pesées pour 12 pièces par exemple)

Par exemple, pour détecter une pièce de monnaie de poids différent lors de trois pesées ($n=3$), le nombre maximal de pièces pouvant être analysées est égal à ${\frac {1}{2}}(3^{3}-1)=13$.

Remarquons qu'avec 13 pièces, on peut en 3 pesées détecter la fausse pièce, mais il n'est pas toujours possible de déterminer sa nature (plus lourde ou plus légère). En général, avec $n$ pesées, on peut toujours déterminer l'identité et la nature de la fausse pièce s'il y a ${\tfrac {1}{2}}(3^{n}-3)$ pièces au plus. Dans le cas de trois pesées, cela donne un maximum de 12 pièces.

Cette version à 12 pièces du problème est apparue dans la presse dès 1945 et Guy et Nowakowski expliquent qu'elle « était en vogue des deux côtés de l'Atlantique pendant la Seconde Guerre mondiale ; il a même été suggéré de la larguer sur l'Allemagne dans le but de saboter leur effort de guerre ».

Solution au problème de pesée de 9 pièces en 2 coups, dans le cas où la pièce différente est plus légère que les autres – si la pièce différente est plus lourde, il faut inverser les deux branches supérieures de chaque décision de pesée.

Le problème des neuf pièces

Cet exemple apparu en janvier 1945 met en scène jusqu'à neuf pièces (ou billes), de poids identique, à l'exception d'une seule, plus légère. La différence n'est perceptible qu'en les pesant, et on ne peut pas mettre d'autres objets lors des pesées. Comment identifier la fausse pièce avec seulement deux pesées ?

Solution

Pour obtenir la solution, on cherche d'abord le nombre maximal de pièces parmi lesquelles on peut trouver la plus légère en une seule pesée. Ce nombre maximal est de trois. Pour trouver la plus légère, on peut comparer deux pièces quelconques, en excluant la troisième. Si les deux pièces ont le même poids, alors la pièce la plus légère est forcément l'une de celles qui ne sont pas sur la balance. Sinon, c'est celle indiquée comme étant la plus légère par la balance.

On imagine maintenant neuf pièces réparties en trois piles de trois. En une seule pesée, on peut déterminer laquelle des trois piles est la plus légère (celle qui contient la pièce la plus légère). Il suffit ensuite d'une seule pesée supplémentaire pour identifier la pièce la plus légère dans cette pile. Ainsi, en deux pesées, on peut trouver une seule pièce plus légère parmi un ensemble de 3 × 3 = 9 .

Par extension, il suffirait de trois pesées pour trouver la pièce plus légère parmi 27 pièces, et de quatre pesées pour la trouver parmi 81 pièces.

Le problème des douze pièces

Cette version comporte douze pièces, dont onze sont identiques. Si l'une d'entre elles est différente, on ignore si elle est plus lourde ou plus légère que les autres. Dans ce cas, on peut déterminer en trois fois pour déterminer s'il existe une pièce différente et, l'isoler et déterminer son poids relatif par rapport aux autres (ce problème et sa solution sont apparus pour la première fois dans un article de 1945).

Solutions

Ce problème admet plusieurs solutions. L'une d'elles, facilement adaptable à un plus grand nombre de pièces, consiste à utiliser une numérotation en base trois : chaque pièce est étiquetée avec un nombre différent de trois chiffres en base trois, puis, à la n -ième pesée, on pèse toutes les pièces dont le n-ième chiffre correspond à celui de l'étiquette du plateau (avec trois plateaux : un de chaque côté de la balance, étiqueté 0 et 2, et un hors plateau, étiqueté 1) .

D'autres procédures, étape par étape, sont similaires à la suivante. Cette méthode est moins directe pour ce problème, et les deuxième et troisième pesées dépendent des opérations précédentes, bien que cela ne soit pas nécessairement le cas (voir ci-dessous).

Quatre pièces sont placées sur chaque plateau. Il y a deux possibilités :

1. Un côté est plus lourd que l'autre.

Dans ce cas, on retire trois pièces du côté le plus lourd, on déplace trois pièces du côté le plus léger vers le côté le plus lourd, et on place trois pièces qui n'ont pas été pesées initialement du côté le plus léger. (Ne pas oublier quelle pièce correspond à quel côté). Il y a trois possibilités :

1.a) Le côté qui était le plus lourd au départ l'est toujours. Cela signifie que : soit la pièce restée sur le côté le plus lourd est plus lourde, soit la pièce restée sur le côté le plus léger est plus légère. En comparant l'une de ces pièces à l'une des dix autres, on détermine laquelle des deux affirmations est vraie et on résout ainsi le problème.

1.b) Le côté le plus lourd lors du premier essai est le plus léger lors du second. Cela signifie que l'une des trois pièces passées du côté le plus léger au côté le plus lourd est la pièce légère. Pour le troisième essai, on pèse deux de ces pièces l'une avec l'autre : si l'une est plus légère, c'est la pièce cherchée ; si elles sont à égalité, la troisième pièce est la pièce légère.

1.c) Les deux côtés ont le même poids. Cela signifie que l'une des trois pièces retirées du côté le plus lourd est la pièce lourde. Pour la troisième tentative, on pèse deux de ces pièces l'une avec l'autre : si l'une est plus lourde, c'est la pièce cherchée ; si elles sont équilibrées, la troisième pièce est la plus lourde.

2. Les deux côtés ont le même poids.

Dans ce cas, les huit pièces sont identiques et peuvent être mises de côté. On prend les quatre pièces restantes et on en place trois d'un côté de la balance. On place trois des huit pièces identiques de l'autre côté. Il y a trois possibilités :

2.a) Les trois pièces restantes sont plus légères. On sait maintenant que l'une de ces trois pièces est différente et qu'elle est plus légère. On prend deux de ces trois pièces et on les pèse l'une avec l'autre. Si la balance penche, alors la pièce la plus légère est différente. Si les deux pièces sont en équilibre, alors la troisième pièce, qui n'est pas sur la balance, est différente et elle est plus légère.

2.b) Les trois pièces restantes sont plus lourdes. On sait donc maintenant que l'une de ces trois pièces est différente et qu'elle est plus lourde. On prend deux de ces trois pièces et on les pèse l'une avec l'autre. Si la balance penche, alors la pièce la plus lourde est différente. Si les deux pièces sont en équilibre, alors la troisième pièce, qui n'est pas sur la balance, est différente et elle est plus lourde.

2.c) Les trois pièces restantes s'équilibrent. Dans ce cas, il suffit de peser la pièce restante par rapport à l'une des 11 autres pour savoir si elle est plus lourde, plus légère ou de même poids.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Balance puzzle » (voir la liste des auteurs).

Voir aussi

• Pesée de la couronne du roi Hiéron II par Archimède