Trois hommes, trois sacs de butin, un canot minuscule et pas un gramme de confiance. Faites-les passer sur l’autre rive — et en aussi peu de traversées que possible.
L’énoncé, publié à Londres en 1917
Traduit intégralement. La dernière phrase est là parce que Dudeney connaissait ses lecteurs.
Il y a bien des années, au temps du contrebandier qu’on appelait « Rob Roy de l’Ouest », une bande de pirates enfouit sur la côte du sud du Devon une quantité de trésor qui fut, bien entendu, abandonnée de la manière inexplicable habituelle. Quelque temps après, l’endroit fut découvert par trois campagnards, qui s’y rendirent une nuit et se partagèrent le butin : Giles prit pour 800 £ de trésor, Jasper pour 500 £, et Timothy pour 300 £. Au retour, ils avaient à franchir la rivière Axe en un point où ils avaient laissé une petite barque toute prête. Mais voici une difficulté qu’ils n’avaient pas prévue. La barque ne pouvait porter que deux hommes, ou un homme et un sac, et ils avaient si peu confiance les uns dans les autres qu’aucun d’eux ne pouvait rester seul, à terre ou dans la barque, avec plus que sa part du butin — quoique deux personnes (se faisant mutuellement contrôle) pussent rester avec plus que leurs parts. Le casse-tête est de montrer comment ils franchirent la rivière en aussi peu de traversées que possible, en emportant leur trésor. Aucun subterfuge — cordes, « ponts volants », courants, nage ou autres astuces du même genre — n’est autorisé.
Henry Ernest Dudeney, Amusements in Mathematics, 1917
Ce qu’on lit aujourd’hui
Douze siècles de la même rivière. Dudeney ouvre cette section de son livre par une généalogie qu’il vaut la peine de citer : le plus ancien exemple connu est de l’abbé Alcuin, né dans le Yorkshire en 735 et mort à Tours en 804 — le maître d’école de Charlemagne. C’est lui qui pose l’ancêtre que tout le monde connaît : le passeur, le loup, la chèvre et le panier de choux. Puis viennent Tartaglia au XVIe siècle, Bachet au XVIIe, et plus près de nous Édouard Lucas, Delannoy, Tarry. Un casse-tête de veillée qui traverse douze cents ans sans une ride, cela mérite qu’on s’y arrête.
Et il est devenu, sans le savoir, l’exemple d’école de l’informatique. Ces énigmes de traversée sont aujourd’hui la première illustration qu’on donne de la recherche dans un espace d’états : on cesse de raisonner sur l’histoire — les sacs, la méfiance, le clair de lune — pour ne plus considérer que des situations, et les passages autorisés de l’une à l’autre. Le problème devient alors un plan de métro qu’il suffit de parcourir. Alcuin n’avait pas ce vocabulaire ; il avait la même idée.
Ce que le problème demande vraiment
Relisez la capacité de la barque : elle est plus étroite qu’il n’y paraît. Deux hommes, ou un homme et un sac. Jamais deux sacs. Jamais un sac tout seul. Et comme il faut quelqu’un pour ramer, tout aller-retour coûte cher. Cette contrainte-là fait plus pour la difficulté que la méfiance des personnages.
La règle de méfiance s’applique aussi dans la barque, et c’est le point que presque tout le monde manque à la première lecture. Un homme seul dans le canot avec un sac est « seul avec du butin » : il ne peut donc jamais transporter plus que sa propre part. Timothy, qui n’a que 300 £, ne peut convoyer que le petit sac. Giles peut tout porter. Voilà qui redistribue les rôles avant même qu’on ait commencé.
Enfin, la clause la plus jolie de l’énoncé : deux personnes ensemble « se faisant mutuellement contrôle » peuvent garder plus que leurs parts. Autrement dit, la surveillance rend honnête. C’est une hypothèse de moraliste victorien, mais c’est surtout une contrainte mathématique très précise — et elle change complètement la structure du problème, puisqu’elle rend certaines situations acceptables à deux qui ne le seraient à personne seul.
Ce que ce problème fait travailler
La modélisation, au sens le plus concret : transformer une histoire de brigands en une liste de situations. Qui est sur quelle rive, quels sacs avec eux, où se trouve la barque — dès qu’on sait écrire cela proprement, le récit disparaît et il ne reste qu’un graphe à parcourir. C’est le même geste que devant les bidons, où l’on ne verse plus de l’eau mais où l’on passe d’un couple de nombres à un autre.
Ensuite, la différence entre une solution et la plus courte. Faire traverser tout le monde n’est pas très difficile si l’on s’autorise vingt allers-retours. Le faire en un minimum de traversées demande de savoir qu’on ne peut pas faire mieux — et donc d’avoir exploré, d’une façon ou d’une autre, tout ce qui était possible avant.
Et une compétence qu’on ne note jamais : tenir ses comptes sans se tromper. Six objets, deux rives, une barque, une dizaine de mouvements — on s’y perd en trois minutes si l’on n’a pas adopté une notation. Dudeney en propose une dans sa solution ; inventez la vôtre avant de la lire, c’est le meilleur de l’exercice.
À vous
- combien de traversées au minimum ? Et comment savez-vous qu’on ne peut pas faire moins ?
- Dudeney remarque en passant que sa solution respecte une condition plus forte que celles de l’énoncé : deux hommes ensemble n’y gardent jamais plus que la somme de leurs deux parts. Exiger cela dès le départ coûterait-il des traversées supplémentaires ?
La seconde question est la vraie, et j’en ai la réponse chiffrée — elle m’a surpris. En commentaire, avec vos notations : j’aimerais bien voir comment vous écrivez tout cela sur une feuille.
Dans la même série. Rétro Math’s reprend les 430 problèmes d’Amusements in Mathematics (1917) : l’énoncé traduit tel quel, ce qu’on en sait aujourd’hui, et la solution en commentaire. Les autres épisodes en ligne : CHINESE MONEY, CHANGING PLACES, THE STOP-WATCH, MRS. PERKINS’S QUILT, WATER, GAS, AND ELECTRICITY, THE INDUSTRIOUS BOOKWORM, SIR EDWYN DE TUDOR, THE NINE COUNTERS, THE SIX FROGS, A CENSUS PUZZLE, THE BARREL PUZZLE, A TRICK WITH DICE.
Problème n° 374 d’Amusements in Mathematics, de Henry Ernest Dudeney (Londres, 1917). Texte et gravure sont dans le domaine public : Dudeney est mort en 1930. Le livre est intégralement disponible sur Project Gutenberg, et l’énoncé original se lit ici.