problème des trois maris jaloux

Trois couples attendent sur une rive avec une barque de deux places. Après chaque traversée, toute femme qui partage une rive avec un homme doit y retrouver son propre mari. Il faut donc choisir les passagers sans rendre dangereuse ni la rive de départ ni celle d'arrivée.

L'énigme devient un jeu de déplacements autorisés. Une situation indique où se trouvent les six personnes et la barque ; une traversée mène à une nouvelle situation. Résoudre le problème revient à enchaîner des situations sûres jusqu'à réunir les trois couples sur l'autre rive.

Le problème des trois maris jaloux est une énigme de traversée sous contraintes. On note M₁, M₂ et M₃ les maris, et F₁, F₂ et F₃ leurs femmes respectives. Les six personnes partent de la même rive. La barque transporte une ou deux personnes à chaque trajet. Une situation est admissible si, sur chaque rive où se trouve au moins un mari, toute femme présente est accompagnée de son propre mari.

La modélisation associe un sommet à chaque situation admissible, en incluant la rive où se trouve la barque. Un arc orienté relie deux sommets lorsqu'une traversée légale fait passer de l'un à l'autre. La situation initiale et la situation finale sont deux sommets particuliers. Chercher une solution revient à établir que le sommet final est accessible depuis le sommet initial par un chemin orienté.

Avec trois couples et une barque de capacité deux, un tel chemin existe. Avec quatre couples, les mêmes règles et la même capacité ne permettent plus la traversée complète. Ajouter une île servant de relais intermédiaire définit une autre variante : sa solubilité dépend des lieux entre lesquels la barque peut circuler, des règles d'accostage et de la contrainte imposée aux personnes présentes sur l'île.

Les couples sont M₁–F₁, M₂–F₂ et M₃–F₃. Tous commencent sur la rive gauche ; la barque a deux places. La flèche → désigne un départ vers la rive droite et la flèche ← un retour vers la rive gauche.

Données : 3 couples ; 6 personnes ; 2 places au maximum ; 2 rives ; la contrainte est contrôlée sur chacune des deux rives après chaque trajet. Le chemin associé comporte douze situations, de la situation initiale à la situation finale.

1. F₁ et F₂ → ; F₁ ←.
2. F₁ et F₃ → ; F₁ ←.
3. M₂ et M₃ → ; M₂ et F₂ ←.
4. M₁ et M₂ → ; F₃ ←.
5. F₁ et F₂ → ; M₃ ←.
6. M₃ et F₃ →.

Le résultat est obtenu en 11 traversées : les six personnes et la barque arrivent sur la rive droite. Pour contrôler la séquence, on examine les deux rives après chaque point-virgule. Toute femme placée avec un ou plusieurs maris y a toujours son propre mari ; lorsqu'une rive ne contient que des femmes, la contrainte y est automatiquement satisfaite.

Pour résoudre l'énigme à la main, on écrit après chaque trajet les occupants des deux rives. Dès qu'une femme se retrouve avec un autre mari sans le sien, on abandonne cette branche et l'on essaie un autre chargement de la barque. Cette méthode convient quand peu de situations restent à examiner.

Pour vérifier systématiquement qu'une solution existe, on préfère le graphe d'états. On ne conserve que les situations admissibles, puis on relie celles qui diffèrent par le déplacement d'une ou deux personnes avec la barque. Une recherche de chemin évite de répéter inutilement une situation déjà explorée.

Pour comparer la version à trois couples avec celle à quatre couples, on reconstruit le graphe avec le nouveau nombre de personnes. L'absence de chemin vers l'arrivée établit le blocage ; si une île est autorisée, il faut l'intégrer comme troisième lieu avant de recommencer l'analyse.

Chemin orienté et chemin hamiltonien. La solution demande seulement un chemin allant de la situation initiale à la situation finale. Elle n'impose pas de visiter une fois et une seule tous les sommets du graphe, condition propre à un chemin hamiltonien.

Chemin possible et chemin le plus court. Une suite de traversées admissibles suffit pour résoudre l'énigme. Affirmer qu'elle est la plus courte exige en plus de comparer sa longueur à celle de tous les autres chemins menant à l'arrivée.

Quatre couples sans relais. Avec une barque limitée à deux personnes et les deux seules rives, le sommet final n'est plus accessible. Il ne faut pas prolonger mécaniquement la solution à trois couples : il faut constater l'absence de chemin dans le nouveau graphe.

Présence d'une île. L'île n'est pas un simple décor : elle ajoute un troisième lieu où les personnes peuvent attendre. Il faut préciser entre quels lieux la barque circule, comment elle accoste et quelle contrainte s'applique sur l'île, puis redéfinir les états et les déplacements. La solubilité de la variante à quatre couples dépend du graphe ainsi obtenu.

Contrôle d'une seule rive. Un chargement peut sembler acceptable du côté où arrive la barque tout en laissant une situation interdite de l'autre côté. Le bon contrôle vérifie séparément les deux rives après chacun des 11 trajets de l'exemple.

Règle modifiée. Changer la capacité de la barque ou le lieu auquel s'applique la contrainte change le graphe et peut changer le verdict. Il faut alors résoudre cette nouvelle variante, et non lui attribuer automatiquement le résultat du problème source.

Le prolongement naturel consiste à construire entièrement le graphe d'états. On peut y distinguer les situations admissibles, les arcs correspondant aux traversées et les sommets réellement accessibles depuis le départ. La comparaison des graphes à trois et à quatre couples fait alors apparaître précisément où l'accès à la situation finale disparaît.

On peut ensuite ajouter l'île comme troisième lieu dans la description d'un état. Cette seule modification oblige à reconstruire les sommets et les arcs ; elle montre comment une hypothèse du modèle transforme une question de possibilité en ouvrant de nouveaux chemins.