problème du loup de la chèvre et du chou

Sur une rive attendent un loup, une chèvre et un chou. Le batelier ne peut embarquer qu’un seul d’entre eux. Il faut donc surveiller ce qui reste à terre après chaque départ : sans le batelier, le loup mangerait la chèvre, et la chèvre mangerait le chou.

L’astuce est d’accepter des retours utiles. La chèvre traverse plusieurs fois, car elle est au centre des deux incompatibilités. L’énigme demande ainsi une suite de déplacements sûrs, pas un simple aller pour chacun.

Le problème du loup, de la chèvre et du chou est une énigme de traversée avec contraintes. Dans sa forme classique, le batelier et au plus un passager occupent la barque. Une situation est interdite si le loup reste avec la chèvre sans le batelier, ou si la chèvre reste avec le chou sans le batelier. Une solution est une suite de traversées qui mène de la rive de départ à l’autre rive sans jamais produire l’une de ces situations.

On peut représenter le problème par un graphe d’états. Chaque sommet décrit la rive occupée par le batelier, le loup, la chèvre et le chou. Deux sommets sont reliés lorsque la barque peut effectuer le déplacement correspondant, et les états interdits sont écartés. Chercher la solution revient alors à trouver un chemin entre l’état initial et l’état final.

L’énigme, attestée dans les Propositions d’Alcuin et rattachée par la source à des origines antiques, possède de nombreuses variantes culturelles, dont « fox, goose and bag of beans » en anglais. Une variante étendue ajoute un bâton et du feu : le bâton ne doit rester ni avec le loup ni avec le feu. Le problème des trois ménages, dit aussi des maris jaloux, relève du même genre, avec des contraintes portant sur les couples. Pour n couples et une barque de capacité n−1, l’existence d’une solution dépend des paramètres.

Au départ, le batelier, le loup, la chèvre et le chou sont sur la même rive. La barque accepte le batelier et un seul passager. Après chaque trajet, il faut contrôler les deux rives.

1. La chèvre traverse, puis le batelier revient seul. Le loup reste avec le chou : cette paire ne présente aucune des incompatibilités données.

2. Le loup traverse, puis la chèvre revient avec le batelier. Ce retour laisse le loup seul sur la rive d’arrivée pendant que le batelier ramène la chèvre sur la rive de départ.

3. Le chou traverse, puis le batelier revient seul. Le loup et le chou peuvent attendre ensemble sur la rive d’arrivée.

4. La chèvre traverse une dernière fois. Les sept trajets sont donc : chèvre, retour seul, loup, chèvre au retour, chou, retour seul, chèvre.

À l’arrivée, les quatre occupants sont réunis. Le contrôle se refait ligne par ligne : chaque fois que le batelier est absent d’une rive, ni le couple loup–chèvre ni le couple chèvre–chou n’y est laissé seul.

Pour résoudre l’énigme classique à la main, on note après chaque traversée les occupants des deux rives. Si une rive sans batelier contient le loup et la chèvre, ou la chèvre et le chou, le déplacement est rejeté.

Quand les objets et les contraintes se multiplient, le graphe d’états remplace avantageusement les essais au hasard. Il conserve seulement les configurations sûres et les relie par les traversées autorisées ; un chemin du départ à l’arrivée fournit alors une solution.

Pour tester une variante, il faut reconstruire les états au lieu de recopier la suite classique. L’ajout du bâton et du feu crée deux incompatibilités supplémentaires, tandis que le problème des trois ménages change les personnages et la règle de sûreté.

Le problème des trois ménages, ou des maris jaloux, appartient au même genre sans être la même énigme. Le critère est la nature des contraintes : ici, elles portent sur loup–chèvre et chèvre–chou ; dans l’autre problème, une femme ne peut rester avec un ou deux hommes en l’absence de son mari.

« Fox, goose and bag of beans » n’est pas une méthode différente, mais une variante culturelle du même schéma de traversée. On reconnaît ce schéma à la barque de capacité limitée et aux deux paires qu’il est interdit de laisser sans surveillance.

Une paire dangereuse n’est interdite que lorsque le batelier est absent de sa rive. Le loup et la chèvre peuvent donc se trouver momentanément sur la même rive avec lui ; les séparer en toute circonstance ajouterait une contrainte absente de l’énoncé.

La capacité « un passager en plus du batelier » est décisive. Dès qu’elle change, les transitions possibles changent aussi ; il faut reconstruire le graphe d’états et ne pas présenter les sept trajets comme une réponse universelle.

La variante avec le bâton et le feu ajoute deux interdictions : bâton–loup et feu–bâton. Une suite sûre pour les trois objets classiques peut donc devenir invalide ; chaque état doit être contrôlé avec l’ensemble des contraintes de la variante.

La généralisation aux n couples n’est pas automatiquement soluble, même avec une barque de capacité n−1. La source indique que l’existence d’une solution dépend des paramètres : il faut donc analyser le cas choisi plutôt que prolonger mécaniquement la solution classique.

Le passage d’une histoire à un graphe d’états ouvre sur l’analyse combinatoire. Cette notion fournit un cadre plus large pour organiser les configurations possibles et étudier les chemins autorisés.