Traversées - Solution
Le chou, la chèvre et le loup.
Il n'est pas trop difficile de trouver la solution en remarquant que le batelier ne peut faire autrement que de laisser le loup seul avec le chou.Une méthode systématique pour ce genre de problème est de tracer le graphe des différents états autorisés sur la rive de départ : chou seul (X), chèvre seule (C), loup seul (L), loup et chou (LX), et les autres cas avec le batelier B.
Et chercher le plus court chemin sur ce graphe entre CXLB et 0, en alternant arcs "aller" et "retour"
Les maris jaloux
Soient a, b, c les femmes et A, B, C leurs maris respectifs.Les seuls états possibles sur la rive de départ sont ceux pour lesquels le complément (la rive d'arrivée) est lui aussi correct. Par exemple aA B serait correct, mais son complément b cC incorrect. aA B est donc rejeté. Restent :
aA bB cC et son complément 0
aA bB C et son complément c
aA B C et son complément b c
aA bB et son complément cC
A B C et son complément a b c
Ainsi que leurs permutations sur les trois couples.
Si on regroupe tous ces états en fonction du nombre de femmes et d'hommes
sans distinction de couples, on obtient le graphe avec les transitions possibles.
Il reste à chercher un trajet reliant le point (3,3) au point (0,0) et alternant
les allers et les retours, puis à choisir les bonnes personnes à chaque état pour
respecter les couples.
Il y a quatre variantes possibles (sans compter les permutations des couples).
Les 6 mouvements centraux sont uniques, seuls les premiers et les derniers varient
(indépendamment, donc 2x2=4 solutions).
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4 couples
Le graphe avec 4 couples s'obtient de même et montre que le problème n'a pas de solution avec un bateau à deux places.
Considérons l'arrivée par un aller au point M (2,2), seul point de passage entre les deux moitié du gtaphe.
On ne peut le quitter qu'en retournant en P (3,3) ou en R (4,2).
Il est donc impossible de passer dans la moitié gauche du graphe.
On ne peut même plus faire passer trois couples, car à un moment une femme au moins resterait seule avec le 4ème couple.
Il faut un bateau à trois places, ce qui rajoute les arcs correspondant.
Il y a alors de nombreuses solutions en 5 allers et 4 retours.
Par exemple 3 femmes (bcd) traversent, une (b) revient, deux hommes (CD) traversent, un couple (cC) revient, les trois hommes (ABC) traversent, la femme (d) revient, trois femmes (bcd) traversent, le mari (A) revient chercher sa femme. |
Autre exemple 2 femmes (cd) traversent, une (c) revient chercher les deux autres (ab), une (a) revient, trois hommes (BCD) traversent, un couple (bB) revient, et traverse avec le dernier homme (A), une femme (b) revient chercher l'autre (a). |
5 couples
Une partie du trajet est obligatoire (en rouge), passant par les points
(5,2), (2,2), (3,3) et (0,3). Pour rejoindre le point (5,2) il y a de nombreuses variantes, de même pour relier le point (0,3) au but.
Par exemple 2 femmes (de) traversent, une (d) revient,
3 femmes (bcd) traversent, une (b) revient,
3 hommes (CDE) traversent, un couple (cC) revient,
les 3 hommes (ABC) traversent, 1 femme (d) revient,
3 femmes (bcd) traversent,
le mari (A) revient chercher sa femme (a).
6 couples et plus
Avec 6 couples, un bateau à 4 places est nécessaire, et avec un bateau à 4 places, on peut faire traverser un nombre quelconque de couples en répètant la manoeuvre : "Deux couples traversent, un couple revient" autant qu'il faut.
Missionnaires et cannibales
Le graphe est le même que celui des maris jaloux en remplaçant
"mari" par "missionnaire"
et "femme" par "cannibale"
Une simplification est que les missionnaires et les cannibales ne sont pas en couples : on peut mettre n'importe quel missionnaire avec n'importe quel cannibale. Seul leur nombre importe.
Le choix est un peu plus restreint si seul un cannibale sait ramer.
La position critique est quand les 3 cannibales se retrouvent sur l'autre rive (passage obligé).
Celui qui doit revenir est le seul qui sait ramer.
Deux misionnaires traversent, un couple revient (le misionnaire rame).
Si maintenant les deux missionnaires traversent de suite,
on ne peut plus ramener le bateau : aucun cannibale sur la rive d'arrivée ne sait ramer !
Il faut d'abord transfèrer le seul cannibale qui sait ramer :
Un missionnaire et le cannibale sachant ramer traversent.
Un missionnaire et un (le) cannibale ne sachant pas ramer reviennent (le missionnaire rame, bien sûr).
Et maintenant les deux misionnaires peuvent traverser : le cannibale sachant ramer étant sur la rive d'arrivée
pourra venir chercher ses collègues com' d'hab'.
Donc si seul un cannibale sait ramer, il faut un aller retour de plus.
