Un jour, un homme étrange m'accosta à l'arrêt de bus. Il avait un petit brin de folie dans les yeux, mais ne semblait pas dangereux. Alors, je pris la décision de ne pas le repousser et écoutai ce qu'il avait à me dire.
- Mon brave Monsieur, je suis désespéré ! Venez-moi en aide !
Quelqu'un qui m'appelle "Mon brave Monsieur", forcément, ça touche ma corde sensible. "Que vous arrive-t-il ?", lui demandai-je alors.
- Voyez-vous, on m'a donné un sac de 80 billes. Elles sont, paraît-il, toutes identiques, sauf l'une d'entre elles qui est légèrement moins lourde que les autres1. Mais elle ne peut être distinguée à l'œil nu !
Je me demandai bien qui pouvait être ce "on" qui s'amusait à distribuer des sacs de billes, mais je n'interrompis pas l'homme.
- On m'a donné la mission de trouver cette intruse à l'aide d'une balance à plateaux que voici2... mais je n'ai le droit qu'à 4 pesées !
L'homme sortit de son sac une balance et la posa par terre. J'eus envie de rire, mais l'air affolé de l'Inconnu me retint. Il avait l'air de prendre toute cette histoire vraiment très au sérieux.
- Aidez-moi, Monsieur, je vous en conjure !
Le bus que j'attendais avait quelques minutes de retard. Après quelques instants de réflexion, je me dis que je pouvais bien me creuser un peu les méninges pour trouver une solution à cette énigme. Et, qui sait, peut-être connaîtrai-je alors le fin mot de l'histoire ?
Je m'assis en tailleur par terre, le sac de billes à mes côtés et la balance devant moi. Resté debout, l'homme trépignait d'impatience et se balançait d'un pied sur l'autre. Je l'ignorai pour mieux me concentrer...
80 billes. 1 balance à plateaux. 4 pesées. 1 bille moins lourde que les autres à trouver.
******************* SOLUTION ************************
La méthode la plus appropriée me semblait être la dichotomie. Je divisai donc mes billes en deux tas de 40 billes chacun, et la balance m'indiqua dans quel tas se trouvait la bille la plus légère.
Je reproduisis l'expérience, avec deux tas de 20 billes, puis deux tas de 10 billes. Je devenais fébrile, sentant que j'étais proche de trouver la solution. Puis, je me rendis compte qu'au bout des quatre pesées autorisées j'avais encore 5 billes dans la main3, qu'il m'était donc impossible de différencier.
Déçu, je relevai la tête, prêt à affirmer à mon interlocuteur que son problème était insoluble. Mais une idée me traversa l'esprit.
Et si, au lieu de diviser mes billes en 2 tas, je les divisais en 34 ?
Ainsi, je constituai 3 tas : 2 tas de 27 billes et un tas de 26, que j'appelai respectivement les tas A, B et C. Je m'apprêtai à mettre les tas A et B sur les plateaux de la balance, tenant ce raisonnement :
Si la balance penche du côté de A, alors la bille la moins lourde est dans B.
Si la balance penche du côté de B, alors la bille la moins lourde est dans A.
Si A et B sont de même poids, alors la bille cherchée est dans C !
Confiant, je m'exécutai. La bille était dans B. Je reproduisis l'expérience en divisant les 27 billes restantes en 3 tas de neuf billes chacun. À l'issue de ma deuxième pesée, il ne me restait plus que 9 billes dans la main !
Lors de la troisième pesée, il ne me restait plus que 3 billes.
Je mis les deux premières sur la balance, et les plateaux s'équilibrèrent. Je savais donc avec certitude que la bille convoitée était la troisième5.
Les yeux brillants de joie, je me relevai et tendis la bille à mon Inconnu. Il me regarda, l'air incrédule. Il s'en saisit et la regarda fixement.
- Vous êtes sûr de vous ?, me demanda-t-il.
- Absolument certain ! lui répondis-je fièrement. Mais puis-je vous demander à quoi rime tout cela ?
L'Inconnu éclata d'un rire étrange et inquiétant. Il me tourna le dos et partit en courant. Et puis, au bout de quelques mètres, il se retourna et m'adressa une phrase sibylline.
- On se retrouvera !
Puis il décampa.
Était-ce une menace ? Une mise en garde ? Quelque chose me dit que je n'allais pas tarder à le découvrir. Un peu sonné, je montai dans mon bus qui venait d'arriver et tentai d'oublier cette étrange rencontre.
Notes
- Savoir que l’intruse est plus légère est une donnée essentielle. Dans une autre version classique, la fausse pièce peut être plus lourde ou plus légère : il faut alors déterminer les deux. C. A. B. Smith étudiait déjà ces variantes dans The Mathematical Gazette en février 1947, notamment le problème des douze pièces à résoudre en trois pesées.↩ Retour au texte
- Ce principe de comparaison est très ancien : le Science Museum Group conserve une balance égyptienne à bras égaux provenant de Tell el-Amarna, datée de 1370–1350 avant notre ère. Des masses connues placées sur un plateau permettaient de peser ce qui reposait sur l’autre.↩ Retour au texte
- Le calcul est bien 80 → 40 → 20 → 10 → 5. En partageant toujours les candidates en deux groupes égaux, on n’exploite que deux réponses : l’équilibre ne peut jamais se produire puisque l’intruse est forcément sur l’un des plateaux.↩ Retour au texte
- Une balance fournit trois réponses possibles : gauche plus lourde, droite plus lourde, équilibre. Trois pesées distinguent donc au maximum 3³ = 27 cas, contre 3⁴ = 81 pour quatre pesées. Avec 80 billes et une intruse connue comme plus légère, quatre pesées constituent ainsi le minimum, à condition d’exploiter aussi l’équilibre.↩ Retour au texte
- Cette comparaison de deux des trois candidates est la quatrième pesée. La méthode fonctionne aussi si l’intruse était initialement dans le tas C de 26 : on compare 9 billes à 9 et on en réserve 8, puis on partage le groupe suspect en 3, 3 et 3, ou en 3, 3 et 2. Une dernière comparaison suffit alors. Les deux plateaux doivent toujours porter le même nombre de billes.↩ Retour au texte
Bravo pour votre réflexion, pour ne pas dire intelligence, mais pourquoi cet article qui me paraît non fini !!
Y aura-t-il une suite ?
Je le souhaite et à bientôt.
Bonjour Eurosix ,
Content d'avoir de vos nouvelles !
Il n'est pas exclu que je continue cette petite histoire à l'occasion, en effet...
A bientôt !
Splendide.