- Problèmes de passage de rivière
-
Sommaire
Historique
Dès le VIIIe siècle, l'abbé de Cantorbéry, Alcuin, proposait des problèmes semblables à celui du chien, de la chèvre et des choux. Au XVIIIe 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.
Les problèmes
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. Laquelle ?
SolutionLes 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 Chien, la Chèvre et les choux
Un fermier doit passer la rivière dans une barque juste assez grande pour lui et son chien, 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 chien. Comment faire passer tout ce monde sans dégâts ?
SolutionUne des possibilités : le fermier emmène la chèvre sur l'autre rive, les choux restant avec le chien. 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 chien sur l'autre rive et le laisse avec les choux tandis qu'il va chercher la chèvre.Le Chien, la Chèvre et les choux, variante
Lulu doit faire passer le chou, la chèvre, le loup (ou le chien), le bâton et le feu de l'autre côté de la rivière. Mais il n'a que deux 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 !!!
SolutionUne 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 Baton 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 baton sur la rive 1. (5) Lulu fait traverser le choux 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 Baton.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. A leur disposition, une feuille d'arbre qui ne peut porter au maximum que 60 g. Comment vont-ils y parvenir ?
Solutiondeux 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 sauterelleLes 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 prendre pas 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 pas 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.
SolutionOn 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 Le missionnaire et les indiens
Il y a 100 ans, un groupe de 3 missionnaires se frayait un chemin dans la forêt amazonienne en compagnie de 3 guides indiens. Arrivés devant une rivière, ils trouvèrent une pirogue qui ne pouvait transporter que 2 personnes à la fois. Elle était difficile à manœuvrer, et ne pouvait l'être que par un seul des 3 Indiens, et par un seul des trois missionnaires. Les missionnaires ne se fiaient guère aux Indiens, et réciproquement les Indiens se méfiaient de la civilisation moderne. Les missionnaires firent donc tout ce qu'il faut pour n'être jamais moins nombreux que les Indiens sur l'une et l'autre des rives. Comment y parvinrent-ils pour un nombre minimal de traversées ?
SolutionSoit I et M respectivement l'indien et le missionnaire pouvant manœuvrer la pirogue, i et m respectivement les indiens et missionnaires ne pouvant manœuvrer la pirogue. P, la pirogue. On a donc la solution en 13 trajets:
Départ Arrivée Iii Mmm * i Mmm Ii Ii Mmm i Mmm Iii I Mmm ii I m ii Mm Ii Mm i m i m Ii Mm ii Mm I m ii I Mmm Iii Mmm i Ii Mmm Ii i Mmm * Iii Mmm Voir aussi
Wikimedia Foundation. 2010.
