Physique

Ce problème récréatif illustre la notion de bilan informationnel : on donne N boules, d'apparences identiques sauf que l'une d'entre elles est peut-être plus lourde ou plus légère que les autres. Combien de pesées sont nécessaires pour identifier l'intruse éventuelle ? On ne dispose que d'une balance à fléau, non graduée. Classiquement, on ne considère que le cas, N=12 qui se règle en k=3 pesées.

La théorie de l'information apporte une solution élégante au problème général. L'information manquante se calcule sur base du logarithme (en base 2) du nombre des solutions possibles, supposées équiprobables, soit, lg(2N+1) bits (Dans le cas, N=12, cela représente lg25 = 4.64386 bits).

L'apport informationnel d'une pesée dépend du nombre de boules que l'on dépose dans chaque plateau. Si on dépose x boules de chaque côté, les probabilités que le fléau penche à gauche, reste en équilibre ou penche à droite valent respectivement :

L'apport d'information se calcule sur base de la formule de Claude Shannon :

Cette fonction est maximum lorsque x=N/3 (soit x=4 dans l'exemple de 12 boules).

Cette pesée favorable apporte lg3 = 1.585 bits par pesée indépendante.

Vu que 3 x 1.585 = 4.75489 > 4.64386 (bits), rien ne semble s'opposer à ce qu'il existe une solution en k=3 pesées dans le cas N=12 (dont l'existence ne peut être établie qu'en la détaillant !).

La solution proposée par John Conway, l'un des mathématiciens les plus inventifs de sa génération, est particulièrement élégante. On détaille l'exemple classique k=3, N=12 mais la généralisation est immédiate, disponible en annexe (Notebook Mathematica).

Quel que soit k, Conway travaille sur un alphabet de 3 lettres, G, D et E, observant qu'il permet de former 3^k = 27 mots distincts de k=3 lettres. De cette liste, il enlève les mots constants, GGG, DDD et EEE, ne retenant que ceux où le premier changement de lettre respecte l'un des schémas GD DE ou EG. Au bilan il reste 12 mots distincts qu'il associe à chacune des 12 boules :

GGD GDG GDD GDE DDE DEG DED DEE EGG EGD EGE EEG

Les trois pesées mettent en balance les boules suivantes :

1:	GGD GDG GDD GDE	DDE DEG DED DEE
2:	GGD EGG EGD EGE	GDG GDD GDE DDC
3:	GDG DEG EGG EEG	GGD GDD DED EGD

où la i^ième pesée place les boules codées par G en i^ième position à gauche et celles codées par D en i^ième position à droite. Chaque pesée fournit un résultat que l'on note, G, si le fléau penche à gauche, D, s'il penche à droite et, E, s'il reste en équilibre. Les trois lettres, prises dans cet ordre, forment un mot qui identifie la boule anormale (Il est alors facile de voir si elle est plus lourde ou plus légère). Si le mot trouvé est EEE, toutes les boules sont identiques. GGG et DDD n'apparaissent jamais.

La méthode de Conway se généralise immédiatement à un nombre plus grand de pesées (et de boules !). La pesée la plus porteuse d'information place x = N/3 boules dans chaque plateau (à condition que N soit divisible par 3 !), amenant lg3 = 1.585 bits. On serait alors tenté de raisonner ainsi : k pesées indépendantes apportent k lg3 (bits) et il faut combler lg(2N+1) bits d'information manquante d'où k pesées devraient venir à bout du problème à N=(3^k-1)/2 boules. C'est un peu vite dit car ce N-là n'est pas multiple de 3 d'où l'information apportée par chaque mesure est inférieure au maximum escompté, 1.585 bits. En fait, (3^k-2)/2 n'est pas davantage multiple de 3, par contre N = (3^k-3)/2 l'est. C'est la solution optimale cherchée et la construction de Conway continue de s'appliquer.

En résumé, k pesées résolvent le problème des (3^k-3)/2 boules et inversement. En particulier, k (= 2,3,4,5, …) pesées suffisent tout juste pour régler le problème comportant 3, 12, 39, 120, …, boules.