Réponse à l'énigme n° 1

 

Notations : H : humain, S : grand singe, s : petit singe.

Une solution optimale est composée de 13 trajets. En voici une, ci-dessous.

Comme il y a deux possibilités pour l' étape 1 et par suite l'étape 2 ( S et s traversent puis S revient OU H et s traversent puis H revient ), et deux possibilités pour l'étape 12 et par suite l'étape 13 ( S revient puis S et s traversent OU H revient puis H et s traversent ), on obtient un total de 4 solutions optimales.

Etapes Rive 1 Rive 2
ETAT INITIAL HHHSss
1. S et s traversent HHHs Ss
2. S revient HHHSs s
3. S et s traversent HHH Sss
4. S revient HHHS ss
5. h et h traversent HS HHss
6. h et s reviennent HHSs Hs
7. h et S traversent Hs HHSs
8. h et s reviennent HHss HS
9. h et h traversent ss HHHS
10.S revient Sss HHH
11.S et s  traversent s HHHSs
12.S revient Ss HHHs
13.S et s traversent HHHSss
Voici un graphe ( signé Daniel Collignon ) détaillant les étapes :
Voici un autre graphe ( signé Daniel Dubuisson ) :
Chaque sommet est noté par trois chiffres et une lettre :
le premier chiffre est le nombre d'hommes
le deuxième chiffre est le nombre de grands singes
le troisième chiffre est le nombre de petits singes
la lettre a désigne la rive initiale et b la rive finale.
On peut passer d'un état à un autre s'il existe un segment entre les deux
points. J'ai élagué les culs-de-sac qui ne feraient qu'augmenter le nombre de
traversées. On doit donc passer de 312a à 312b.
On voit donc qu'il n'existe que quatre manières distinctes de réaliser la traversée en 13 trajets.
Les choix sont très limités et les passages obligés nombreux.