Problème — 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.