Probleme – Un graphe pour un problème qui n'en a pas l'air

1. Le modèle. Le mot « état » est la clé : un sommet est une situation, un arc est un coup.

• Sommets : les couples $(a,b)$ avec $0\le a\le 3$ et $0\le b\le 5$, où $a$ et $b$ sont les contenus des deux seaux. Il y en a $4\times 6=24$.
• Arcs : de $(a,b)$ partent au plus six coups — remplir $A$, remplir $B$, vider $A$, vider $B$, verser $A$ dans $B$, verser $B$ dans $A$ —, chacun menant à un état bien déterminé. On écarte les coups sans effet.

Mesuré : $n=24$ sommets et $m=106$ arcs, soit un degré sortant moyen de $4,42$.

Ce que ce comptage décide. Le graphe est minuscule : n'importe quel algorithme convient, y compris un $O(n^2)$. Mais le même modèle appliqué à des seaux de $1000$ et $1001$ litres donnerait un million d'états, et à trois seaux de $100$ litres, un million également. Le graphe des états explose avec le nombre de variables, et c'est pourquoi le chapitre insiste sur les ordres de grandeur avant tout algorithme : on compte les sommets avant de choisir la méthode. C'est la mise en garde du chapitre chap:exploration.

2. La résolution. La question « le moins de coups possible » est une question de plus court chemin dans un graphe non pondéré, donc un parcours en largeur depuis $(0,0)$. Mesuré : la solution est en six coups.

Le parcours en largeur ne fait pas que trouver une solution : il prouve qu'il n'en existe pas de plus courte, puisqu'il découvre les états par distance croissante. Une recherche en profondeur trouverait une solution, mais sans cette garantie — c'est la distinction du chapitre chap:parcours.

Mesuré également : l'excentricité de $(0,0)$ — la plus grande distance à un état atteignable — vaut $7$. Aucun état ne demande plus de sept coups.

3. Les états inatteignables. Mesuré : $16$ des $24$ états sont atteignables depuis $(0,0)$, et les $8$ manquants sont exactement

$$\{(a,b):a\in \{1,2\},b\in \{1,2,3,4\}\},$$

c'est-à-dire les états où aucun des deux seaux n'est ni vide ni plein.

Démonstration. C'est un invariant. Examinons les six coups : remplir met un seau à sa capacité ; vider met un seau à zéro ; verser $A$ dans $B$ s'arrête soit quand $A$ est vide, soit quand $B$ est plein. Après tout coup, au moins un seau est vide ou plein. L'état initial $(0,0)$ vérifie la propriété ; elle est donc vraie de tout état atteignable, par récurrence sur le nombre de coups.

C'est ainsi qu'on démontre l'impossibilité dans un graphe d'états : non pas en explorant, mais en exhibant une propriété vraie au départ et conservée par tous les arcs. Le parcours, lui, ne fait que confirmer — il donne le nombre $16$, l'invariant donne la raison.

4. Les seaux de $4$ et $6$ litres. Mesuré : $5$ litres sont impossibles ; $2$ litres sont atteints en deux coups — remplir le seau de $6$, verser dans celui de $4$.

Le critère général : les quantités atteignables sont exactement les multiples de $\mathrm{pgcd}(A,B)$ compris entre $0$ et $\max (A,B)$. Chaque coup ajoute ou retranche un multiple de $A$ ou de $B$ au contenu total, donc tout contenu s'écrit $\alpha A+\beta B$ avec $\alpha ,\beta$ entiers, et le théorème de Bézout dit que ces combinaisons sont exactement les multiples du pgcd. Ici $\mathrm{pgcd}(4,6)=2$ : $5$ est impair, donc hors d'atteinte ; $2$ est un multiple de $2$, donc accessible. Et $\mathrm{pgcd}(3,5)=1$ explique que toute quantité de $0$ à $5$ soit atteignable avec les seaux du départ. Vérifié sur quatre couples de capacités.

Ce que ce problème enseigne, et c'est la thèse du chapitre. « Presque tout devient un graphe » n'est pas une figure de style. Ici il n'y avait ni réseau, ni carte, ni relation entre objets — seulement un jeu. Le graphe est apparu dès qu'on a nommé les états et les transitions, et la question « en combien de coups ? » est devenue mécaniquement un plus court chemin. C'est exactement le procédé qui modélise le taquin, le Rubik's cube, un automate fini (chapitre chap:automates) ou l'ordonnancement d'un atelier. Le travail d'informaticien n'est pas de trouver l'algorithme : c'est de reconnaître le graphe. L'algorithme, lui, était écrit depuis longtemps.