Problèmes de passage de rivière

Les problèmes de passage de rivière sont des exercices relevant de jeux mathématiques ou de réflexions. Certains sont très anciens, tels ceux posés au VIII^e siècle par l'abbé de Cantorbéry, Alcuin, dont le plus connu est le problème du loup, de la chèvre et des choux^[1]. Plus récemment, au XVIII^e siècle, les habitants de Koenigsberg, en Prusse-Orientale, se demandèrent s'il était possible de passer tous les ponts de leur ville sans jamais emprunter deux fois le même chemin. Le mathématicien Leonhard Euler examina le problème, en démontra l'impossibilité, et fonda la topologie, nouvelle discipline de mathématiques. Ce problème est dénommé problème des sept ponts de Königsberg. Ce type de problème présente encore aujourd'hui un intérêt mathématique en lien avec la théorie des graphes.

Les problèmes

La traversée nocturne

C'est la nuit noire et 4 personnes (Alex, Bob, Carla et Dom) se trouvent bloquées sur une des berges de la rivière où se trouve un pont suspendu. Nos aventuriers sont équipés d'une seule torche. Par ailleurs, on sait qu'Alex met 1 minute pour traverser le pont, Bob en met 2, Carla 5 et Dom 10. Pour traverser le pont, ils sont obligés de s'équiper de la torche et le pont supporte au maximum deux personnes. De plus, si deux personnes traversent le pont en même temps, elles iront au rythme de la personne la plus lente. Quelle est, selon vous, la méthode la plus rapide pour traverser le pont^[2]^,^[3] ?

Solution

Ils peuvent mettre 17 minutes. Voici le scénario pour y arriver : Alex et Bob traversent en premier le pont avec la torche, ils mettent 2 minutes, puis Bob revient avec la torche (Total=4 minutes). Bob reste sur la première berge et laisse partir Carla et Dom qui rejoignent l'autre berge en 10 minutes (Total=14 minutes). Enfin Alex prend la torche pour la ramener à Bob sur la première berge et ils reviennent ensemble (Total=17 minutes).

Le détachement

Un détachement de soldats arrive devant une rivière. Le pont a sauté, et le courant est trop fort pour que l'on s'y risque à la nage. Le capitaine réfléchit, et aperçoit un petit bateau manœuvré par deux garçons. Il le réquisitionne, mais s'aperçoit que le bateau est juste assez grand pour un seul soldat ou deux enfants, trop petit pour un soldat et un enfant. Le capitaine, cependant, trouve une solution^[4]. Laquelle ?

Solution

Les enfants passent en bateau sur la rive opposée. L'un d'eux reste là pendant que l'autre revient. Un soldat passe alors la rivière. L'enfant sur la rive opposée ramène le bateau. Les 2 enfants gagnent la rive opposée, et l'un d'eux reste pendant que l'autre ramène le bateau. Un deuxième soldat passe la rivière et l'enfant de la rive opposée ramène le bateau. Ils continuent ainsi jusqu'à ce que tout le détachement se retrouve sur l'autre rive.

Le loup, la chèvre et les choux

Un fermier doit passer la rivière dans une barque juste assez grande pour lui et son loup, ou lui et sa chèvre, ou lui et ses choux. Les choux seront mangés s'il les laisse seuls avec la chèvre, et la chèvre sera mangée s'il la laisse seule avec le loup. Comment faire passer tout ce monde sans dégâts^[5] ?

Solution

Une des possibilités : le fermier emmène la chèvre sur l'autre rive, les choux restant avec le loup. Il retourne prendre les choux, qu'il laisse sur l'autre rive, car il ramène la chèvre à son point de départ. Puis il passe le loup sur l'autre rive et le laisse avec les choux tandis qu'il va chercher la chèvre.

Le loup, la chèvre et les choux, variante

Lulu doit faire passer le chou, la chèvre, le loup, le bâton et le feu de l'autre côté de la rivière. Mais il n'a que trois places sur son bateau !

De plus, si la chèvre et le chou sont ensemble sur une rive quand Lulu s'éloigne, la chèvre mange le chou. Si le loup et la chèvre sont ensemble quand Lulu s'éloigne, le loup mange la chèvre. Si le bâton et le loup sont ensemble quand Lulu s'éloigne, le bâton bat le loup. Si le feu et le bâton sont ensemble quand Lulu s'éloigne, le feu brûle le bâton !!!

Solution

Une des possibilités : Lulu emmène la chèvre et le bâton dans son bateau mais ne dépose que la chèvre sur l'autre rive, il revient avec le bâton, le dépose sur la rive 1 tandis qu'il prend le Feu et le loup. il les dépose sur la rive 2 et reprend la chèvre, laissant le feu avec le loup. Lulu redépose la chèvre et prend le chou qu'il dépose sur l'autre rive. Il revient à vide, laissant le feu, le loup et le chou, tandis que, dernier voyage, il va chercher la chèvre et le bâton.

Autre possibilité (en 7 trajets): (1) Lulu transporte d'abord Chèvre et Bâton sur la rive 2. (2) Lulu revient à vide chercher le loup et (3) le dépose également sur la rive 2. (4) Lulu ramène chèvre et bâton sur la rive 1. (5) Lulu fait traverser le chou et le feu et les dépose sur la rive 2 en compagnie du loup. (6) Lulu revient à vide puis (7) refait traverser chèvre et Bâton.

Le lombric, le millepattes et la sauterelle

Un lombric de 50 g, un millepatte de 30 g et une sauterelle de 20 g veulent passer la rivière. À leur disposition, une feuille d'arbre qui ne peut porter au maximum que 60 g. Comment vont-ils y parvenir ?

Solution

Deux possibilités : La sauterelle passe avec le millepatte et revient. Le lombric passe ensuite. Le millepatte revient chercher la sauterelle. Pour la seconde solution, c'est le millepatte qui revient au lieu de la sauterelle.

Les quatre couples

Quatre couples sont tout juste fiancés : Annie avec Armand, Béatrice avec Bernard, Caroline avec Charles, et Delphine avec Denis. Ils veulent pique-niquer de l'autre côté de la rivière. Ils peuvent louer une barque, mais qui ne peut pas prendre plus de 2 personnes à la fois. Les hommes sont d'une jalousie terrible, et aucun ne veut laisser sa fiancée en compagnie d'un autre homme même en public, à moins que lui-même ne soit présent. Armand ne souffrira pas de voir Annie avec Bernard en son absence. Il y a au milieu de la rivière une île qui peut servir d'étape pendant la traversée. Le problème est de savoir comment traverser la rivière par le nombre minimum d'allées et venues. Aller de la rive à l'île ou de l'île à la rive compte pour un voyage, de même que d'aller d'une rive à l'autre. Tout le monde sait ramer. La seule contrainte provient de la jalousie des hommes : aucun d'eux ne peut prendre le bateau lorsqu'une femme autre que sa fiancée est seule soit sur l'île, soit sur l'autre rive, même s'il a une autre destination. 17 voyages suffisent.

Solution

On note a=Annie, A=Armand, b=Béatrice, B=Bernard, c=Caroline, C=Charles, d=Delphine, et D=Denis. Le tableau ci-dessous indique la situation des 8 personnes entre les traversées.

cette rive	île	autre rive
ABCDabcd	*	*
ABCDcd	*	ab
ABCDbcd	*	a
ABCDd	bc	a
ABCDcd	b	a
CDcd	b	ABa
BCDcd	b	Aa
BCD	bcd	Aa
BCDd	bc	Aa
Dd	bc	ABCa
Dd	abc	ABC
Dd	b	ABCac
BDd	b	ACac
d	b	ABCDac
d	bc	ABCDa
d	*	ABCDabc
cd	*	ABCDab
*	*	ABCDabcd

Références culturelles

Le problème du loup, de la chèvre et des choux est mis en scène dans l'épisode Maggie s'éclipse des Simpson.
Ce même problème est au cœur de l'intrigue du livre pour enfants L'ogre, le loup, la petite fille et le gâteau de Philippe Corentin.
Il se retrouve à la fin du jeu vidéo Les Chevaliers de Baphomet : Le Manuscrit de Voynich. Ici Horus doit amener le meurtrier, le témoin et le frère de la victime au tribunal mais est le seul à pouvoir traverser la rivière à gué et il ne peut transporter qu'une personne à la fois (le meurtrier tuerait le témoin s'ils sont seuls, ainsi que le frère de la victime tuerait le meurtrier). Le nombre de 7 traversées est imposé.
Dans le livre/cahier de vacances Le labyrinthe des dragons (C. Lambert et A. Popet), le problème est posé au chapitre 6, en utilisant les personnages de l'histoire.
Dans la saison 1 de la série Fargo, une variante de ce problème (avec un renard, un lapin et un chou) est mentionnée deux fois par l'agent Bill Budge : la première auprès de son partenaire, l'agent Webb Pepper (qui suggère de faire une tourte des trois pour résoudre le problème), et la seconde auprès de Lester Nygaard (qui donne la réponse attendue).

Références

↑ Pierre Legrand, Enigmes carolingiennes, Bulletin de l'APMEP, n°512, janvier-février 2015, p.25-35
↑ (en) Günter Rote, « Crossing the bridge at night »
↑ Jean-Paul Delahaye, La traversée du pont, Pour la Science, n°324, octobre 2004, p.90-95
↑ Ce problème est une variante du problème 19 d'Alcuin, propositiones ad acuendos iuvenes, Proposition de viro et muliere ponderantibus.
↑ Alcuin, propositiones ad acuendos iuvenes, problème 18, Proposition de homine et capra et lupo.