problème de pesées

Imaginez neuf boules identiques à l’œil, mais dont l’une est connue pour être plus lourde. Une balance à deux plateaux permet seulement de constater quel côté descend ou si les deux côtés restent au même niveau. Chaque pesée sépare donc les possibilités en trois résultats : gauche plus lourde, droite plus lourde ou équilibre.

Le problème consiste à organiser ces choix pour trouver la boule en très peu de pesées. Une première comparaison de trois boules contre trois autres laisse trois groupes possibles de trois boules. Une seconde comparaison suffit alors à isoler la coupable dans le groupe retenu.

Un problème de pesées demande d’identifier, parmi n objets de même apparence, un objet dont la masse diffère, en limitant le nombre de comparaisons avec une balance de Roberval. Cette balance ne donne pas une masse numérique : elle indique seulement un déséquilibre à gauche, un déséquilibre à droite ou l’équilibre. La stratégie doit donc associer chaque résultat possible à un sous-ensemble de candidats.

Dans la variante où l’on sait que la boule intruse est plus lourde, une pesée peut répartir les candidats en trois groupes. Avec k pesées, le nombre maximal de suites de résultats est $3^{k}3^k$ ; il faut donc au minimum que le nombre de candidats soit inférieur ou égal à cette quantité. Pour neuf boules et deux pesées, $9\le 3^2=99\backslash leq\; 3^2=9$ : la limite théorique est atteinte.

Si l’on ignore à l’avance si l’intruse est plus lourde ou plus légère, chaque boule correspond à deux hypothèses. Les comparaisons doivent alors distinguer ces hypothèses tout en tenant compte des boules déjà utilisées comme témoins. La stratégie et le nombre minimal de pesées changent donc selon la variante annoncée.

Considérons neuf boules nommées A, B, C, D, E, F, G, H et I. Une seule est plus lourde que les autres, et cette information est connue. La première pesée compare A, B, C à D, E, F. Les trois résultats sont traités séparément.

Si les deux plateaux s’équilibrent, l’intruse se trouve parmi G, H et I, car les six premières boules ont été comparées par groupes de même taille. Si le plateau gauche descend, l’intruse est parmi A, B et C. Si le plateau droit descend, elle est parmi D, E et F. Dans les deux derniers cas, la boule intruse appartient au groupe placé sur le plateau qui descend.

La deuxième pesée compare ensuite les deux premières boules du groupe retenu. Pour le groupe A, B, C, on compare A à B ; pour D, E, F, on compare D à E ; pour G, H, I, on compare G à H. Si l’un des deux plateaux descend, la boule correspondante est l’intruse. Si les plateaux s’équilibrent, la troisième boule du groupe est l’intruse. Deux pesées suffisent donc dans tous les cas.

Pour construire une stratégie, commencez par dénombrer les hypothèses réellement possibles : une boule précise et, éventuellement, le fait qu’elle soit plus lourde ou plus légère. Associez ensuite chaque pesée à des groupes aussi équilibrés que possible. Les deux plateaux doivent porter le même nombre de boules ; interprétez la comparaison selon les hypothèses encore ouvertes (candidate plus lourde ou plus légère), sans exiger que les boules candidates soient déjà connues normales.

Après chaque résultat, éliminez toutes les hypothèses incompatibles plutôt que de recommencer le raisonnement. Une stratégie est optimale lorsqu’elle garantit l’identification dans le nombre de pesées annoncé, y compris dans le résultat qui laisse le plus de candidats.

Une balance de Roberval ne mesure pas directement la masse d’une boule : elle compare deux ensembles placés sur ses plateaux. Un résultat d’équilibre signifie que les masses totales comparées sont égales, pas que chaque boule est normale.

Il ne faut pas confondre la variante où l’intruse est connue plus lourde avec celle où elle peut être plus lourde ou plus légère. Dans la première, chaque boule fournit une seule hypothèse. Dans la seconde, une boule fournit deux hypothèses et une stratégie valide doit aussi déterminer le sens de l’écart.

Enfin, une borne fondée sur trois résultats par pesée indique seulement ce qui est théoriquement possible. Elle ne fabrique pas automatiquement une stratégie : la disposition concrète des boules doit encore rendre chaque branche réalisable et non ambiguë.

Le comptage en trois résultats suppose une balance fiable et une boule intruse dont la masse diffère suffisamment pour que le déséquilibre soit observable. Une balance qui fournit une masse, ou une mesure entachée d’incertitude, relève d’un autre modèle de problème.

Dans la variante inconnue, il faut distinguer « la boule A est plus lourde » de « la boule A est plus légère ». De plus, une pesée déséquilibrée impose des contraintes croisées : une boule posée à gauche peut être la lourde recherchée, tandis qu’une boule posée à droite peut être la légère recherchée. Les témoins et les résultats précédents deviennent essentiels.

La borne $3^{k}3^k$ porte sur le nombre d’hypothèses distinctes à séparer, et ne garantit donc pas à elle seule l’existence d’un protocole pour chaque nombre de boules. Dans la variante où le sens de l’écart est inconnu, il faut compter les hypothèses « boule précise plus lourde » et « boule précise plus légère », sous les contraintes imposées par les témoins et les pesées précédentes. La construction et la vérification de l’arbre des pesées établissent seules la validité de la stratégie. Un groupe vide ou un nombre de candidats non divisible par trois peut être traité, mais il faut alors accepter des branches de tailles différentes.

Chaque pesée peut être vue comme une question à trois réponses. Cette lecture relie les problèmes de pesées à la théorie de l’information : une stratégie efficace cherche à réduire fortement l’incertitude à chaque étape, tandis qu’une borne inférieure mesure le nombre de réponses nécessaires pour séparer toutes les hypothèses.

L’[analyse combinatoire](/articles/glossaire-analyse-combinatoire) fournit le langage du dénombrement des candidats et des branches. La [Théorie de l'information](/articles/glossaire-theorie-de-l-information) éclaire ensuite le lien entre nombre d’hypothèses, nombre de résultats et profondeur minimale d’un arbre de décision. Les variantes plus riches ajoutent des boules témoins, des masses possibles multiples ou des pesées dont la fiabilité est limitée.