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.
Les programmes sont publics, avec de quoi refaire le calcul : github.com/w0uf/retro-maths-dudeney. Attention, les solutions y sont données.
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, THE MILKMAID PUZZLE, THE TROUBLESOME EIGHT, THE FOUR POSTAGE STAMPS, A CHAIN PUZZLE, THE ROUND TABLE, THE CAB NUMBERS, THE POTATO PUZZLE, THE ECCENTRIC CHEESEMONGER, THE CLUB CLOCK, THE TWELVE MINCE-PIES.
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.
Les réponses, comme promis — et le chiffre qui m’a surpris.
1. Treize traversées. Voici celles de Dudeney, que j’ai rejouées une à une. J’écris G, J et T pour Giles, Jasper et Timothy, et je désigne les sacs par leur valeur.
1. Jasper passe avec les 500 £.
2. Jasper revient seul.
3. Giles passe avec les 300 £.
4. Giles revient seul.
5. Jasper et Timothy passent ensemble.
6. Timothy revient avec les 300 £.
7. Giles passe avec les 800 £.
8. Jasper revient avec les 500 £.
9. Jasper et Timothy passent ensemble.
10. Giles revient seul.
11. Giles passe avec les 300 £.
12. Jasper revient seul.
13. Jasper passe avec les 500 £.
Remarquez le milieu : aux traversées 6 et 8, deux sacs déjà passés repartent en arrière. C’est ce que personne n’essaie spontanément, et c’est ce qui débloque tout. Remarquez aussi que Timothy ne touche jamais qu’au petit sac, comme l’énoncé l’y oblige.
Comment sait-on qu’on ne peut pas faire moins ? En renonçant à être malin. Une situation, c’est : qui est sur quelle rive, avec quels sacs, et où est la barque. En partant du début et en ne franchissant que les passages permis, on n’atteint en tout que 48 situations. Un programme les visite par ordre d’éloignement — toutes celles à une traversée, puis à deux, puis à trois — et la situation finale n’apparaît qu’au treizième rang. Il n’y a rien à démontrer de plus : tout ce qui était possible en douze traversées a été regardé, et l’arrivée n’y était pas. Quarante-huit cases, cela se fait encore à la main sur une grande feuille ; Alcuin n’aurait pas procédé autrement.
Autre résultat du même parcours : il existe 50 façons différentes de réussir en treize traversées. Celle de Dudeney en est une.
2. La condition plus forte ne coûte rien — et elle fait le ménage. Exigeons maintenant, dès le départ, que deux hommes laissés ensemble ne gardent jamais plus que la somme de leurs deux parts. On s’attend à payer cette prudence d’une ou deux traversées. Il n’en est rien : le minimum reste treize. Mais des cinquante solutions, il n’en survit que huit. Plus de quatre sur cinq disparaissent.
Voilà ce qui m’a surpris. Dudeney présente la chose comme une remarque de fin de page — « bien que ce dernier point n’ait pas été exigé dans les conditions » — et l’on croit à une coquetterie. C’en est le contraire : parmi cinquante solutions également courtes, il a choisi l’une des huit où personne, à aucun moment, seul ou à deux, n’a sous la main plus que son dû. Sa solution n’est pas seulement la plus courte, elle est la plus honnête. Pour des cambrioleurs, c’est un luxe ; pour un auteur de casse-tête, c’est une signature.
Et vos notations ? La sienne tient en trois colonnes : la rive de gauche, la rivière, la rive de droite, une ligne par traversée, avec une parenthèse pointue pour indiquer le sens de la barque. La mienne est plus fruste, vous venez de la lire. Si vous en avez trouvé une qui tient sur une demi-feuille, elle m’intéresse.