Deux cruches, une équation : du problème 3–5 à Bézout

Deux cruches non graduées, une source d’eau et un objectif précis : mesurer une quantité qui n’est indiquée sur aucun récipient. Le problème est concret, mais il mène naturellement aux entiers, au plus grand commun diviseur, à l’identité de Bézout et aux algorithmes de graphes.

Le critère arithmétique indique si l’objectif satisfait le test de divisibilité ; les contraintes de capacité et les états des cruches déterminent s’il est physiquement réalisable et comment. Ce sont des réponses différentes et complémentaires.

1. Règles et objectif

Dans le modèle ouvert classique, nous disposons d’une source d’eau illimitée, d’une évacuation et de deux cruches non graduées de capacités entières. Une action autorisée est exactement l’une des suivantes :

• remplir complètement une cruche à la source ;
• vider complètement une cruche dans l’évacuation ;
• transvaser une cruche dans l’autre jusqu’à ce que la première soit vide ou que la seconde soit pleine.

On ne peut pas interrompre un transvasement à vue d’œil. Dans le problème principal, les capacités sont de 3 et 5 litres et l’objectif strict est (1,0) : un litre dans la cruche de 3 litres et la cruche de 5 litres vide. Nous écrivons toujours un état sous la forme (u,v), où u est le contenu de la cruche de 3 litres et v celui de la cruche de 5 litres.

2. Le cas 3–5, état par état

Des cruches vides à un litre isolé

Étape	Action	État	Résultat de l’action
0	Départ	(0,0)	Les deux cruches sont vides
1	Remplir la cruche de 3	(3,0)	La cruche est pleine
2	Verser de la 3 dans la 5	(0,3)	La cruche de 3 se vide
3	Remplir de nouveau la 3	(3,3)	La cruche est pleine
4	Verser de la 3 dans la 5	(1,5)	Il ne reste que 2 litres de place dans la cruche de 5
5	Vider la cruche de 5	(1,0)	Le litre recherché reste isolé

(0,0) → (3,0) → (0,3) → (3,3) → (1,5) → (1,0)

Chaque flèche respecte les règles et chaque coordonnée reste comprise entre zéro et la capacité correspondante. Ces deux contrôles simples révèlent de nombreuses fausses solutions.

3. État, bilan et invariant

Il est utile de tenir deux registres. L’état physique dit où se trouve l’eau ; le bilan dit combien d’eau est présente au total et comment elle est entrée ou sortie. Pour le chemin précédent :

État physique et bilan avec l’extérieur

État	Total présent	Bilan avec l’extérieur
(0,0)	0	0
(3,0)	3	3
(0,3)	3	3
(3,3)	6	2 · 3
(1,5)	6	2 · 3
(1,0)	1	2 · 3 − 5

Pendant un transvasement, le total u + v est invariant : seule sa répartition change. Remplir ou vider échange de l’eau avec l’extérieur. Sur ce chemin, deux contenus complets de 3 litres entrent et le contenu complet d’une cruche de 5 litres sort, donc :

1 = 2 · 3 − 5

Il existe un invariant arithmétique plus général : tout volume accessible est une combinaison entière des capacités. Au départ, il n’y a que zéro ; remplir introduit une capacité, vider introduit zéro, et un transvasement produit des sommes ou des différences avec une capacité lorsqu’une cruche se vide ou que l’autre se remplit. L’ensemble des combinaisons entières reste donc stable par toutes les actions autorisées.

La paire de coefficients n’est ni l’état physique ni unique. C’est une étiquette algébrique qui certifie un volume ; l’état (u,v) demeure la description physique indispensable.

4. Le sens des coefficients négatifs

Le chemin fournit une équation diophantienne, c’est-à-dire une équation dont les solutions recherchées doivent être des nombres entiers :

3x + 5y = 1,
x = 2, y = −1.

Le coefficient −1 ne représente pas une quantité d’eau négative. Dans le bilan, il indique que le contenu complet de 5 litres a été versé dans l’évacuation. Les coefficients comptent des contributions signées ; les contenus réels restent toujours entre zéro et les capacités.

Cette interprétation comme décompte net est directe pour les chemins canoniques, où une cruche n’est remplie que lorsqu’elle est vide et n’est vidée dans l’évacuation que lorsqu’elle est pleine. Si l’on remplit ou vide une cruche partiellement pleine, les coefficients restent un certificat algébrique, mais ne coïncident plus avec un simple nombre d’actions.

Cette distinction évite une confusion fréquente : une solution entière de l’équation est un certificat arithmétique, pas encore une liste automatique de remplissages et de transvasements. Pour obtenir les actions, il faut construire un chemin entre états autorisés.

5. Algorithme d’Euclide étendu et identité de Bézout

Le plus grand commun diviseur de deux entiers positifs est le plus grand entier positif qui les divise tous les deux. L’algorithme d’Euclide le calcule ; en remontant ses divisions, on obtient aussi les coefficients de Bézout :

5 = 1 · 3 + 2
3 = 1 · 2 + 1

1 = 3 − 2
  = 3 − (5 − 3)
  = 2 · 3 − 5

Nous retrouvons exactement le bilan du chemin. L’identité de Bézout affirme que, pour des entiers positifs a et b, il existe des entiers r et s tels que :

a r + b s = PGCD(a,b)

Multiplier l’identité par un entier produit tous les objectifs multiples du PGCD. Pour 3x + 5y = 1, à partir de la solution (2,−1), toutes les solutions entières sont :

x = 2 + 5t
y = −1 − 3t,  où t est entier.

Cette infinité algébrique ne signifie pas qu’il existe une infinité d’états physiques : les capacités sont finies et de nombreuses paires de coefficients décrivent le même volume sans suggérer un chemin commode.

6. La règle générale et ses limites

Pour des capacités a et b et un objectif d, l’équation associée est :

a x + b y = d

Posons g = PGCD(a,b). L’équation possède des solutions entières si et seulement si g divise d. Dans le modèle ouvert classique, pour laisser exactement d litres dans une seule cruche avec l’autre vide, il faut aussi :

0 ≤ d ≤ max(a,b).

Avec les actions standard, ces deux conditions sont également suffisantes. La divisibilité exclut les objectifs arithmétiquement impossibles ; la borne de capacité exclut les quantités qu’aucune cruche ne peut contenir. L’équation ax + by = d concerne le total présent : pour le rendre égal à d, l’autre cruche doit réellement être vide à la fin. Si l’on s’arrêtait avec d dans une cruche et encore de l’eau dans l’autre, le total ne serait pas d.

7. La comparaison 4–6 : un litre non, deux litres oui

Pour des cruches de 4 et 6 litres, PGCD(4,6) = 2. Toute combinaison 4x + 6y est paire ; un litre est donc impossible. Nul besoin de tâtonner : la parité est un invariant.

Deux litres sont possibles car 2 = 6 − 4 :

(0,0) → (0,6) → (4,2) → (0,2)

Les états sont ordonnés comme (cruche de 4, cruche de 6) : on remplit la 6, on verse dans la 4 jusqu’à la remplir, puis on vide la 4. Il reste 2 litres dans la 6 et l’autre cruche est vide.

8. D’autres cas vérifiés

Cruches 3–5, objectif 4

Le certificat est 4 = 2 · 5 − 2 · 3. Avec les états ordonnés comme (3,5) :

(0,0) → (0,5) → (3,2) → (0,2)
      → (2,0) → (2,5) → (3,4) → (0,4)

Chaque transvasement continue jusqu’à vider sa source ou remplir sa destination ; l’état final contient 4 litres dans la cruche de 5.

Cruches 2–7, objectif 1

Ici 1 = 7 − 3 · 2. Avec les états ordonnés comme (2,7) :

(0,0) → (0,7) → (2,5) → (0,5)
      → (2,3) → (0,3) → (2,1) → (0,1)

On soustrait successivement des portions de 2 litres à la cruche de 7.

Cruches 6–10, objectif 8

PGCD(6,10)=2 divise 8. Un certificat est 8 = 3 · 6 − 10 ; le chemin suivant permet d’obtenir la même quantité avec un autre bilan, 8 = 2 · 10 − 2 · 6. États ordonnés comme (6,10) :

(0,0) → (0,10) → (6,4) → (0,4)
      → (4,0) → (4,10) → (6,8) → (0,8)

Cruches 6–9, objectif 4

C’est impossible : PGCD(6,9)=3 ne divise pas 4. Tous les volumes accessibles sont multiples de 3.

9. La variante fermée 8–5–3

Un autre classique utilise trois récipients de 8, 5 et 3 litres. Les hypothèses changent : le récipient de 8 litres est plein au départ, il n’existe ni source ni évacuation, et seuls les transvasements complets sont permis, jusqu’à vider la source ou remplir la destination. Il faut partager les 8 litres en deux parts de 4.

En écrivant les états dans l’ordre (8,5,3), une solution est :

(8,0,0) → (3,5,0) → (3,2,3) → (6,2,0)
        → (6,0,2) → (1,5,2) → (1,4,3) → (4,4,0)

Le total vaut toujours 8 : la conservation de l’eau est ici l’invariant dominant. On ne peut pas appliquer sans modification le critère des deux cruches avec source et évacuation ; il y a trois capacités, un système fermé et un objectif de partage. Il faut énoncer les hypothèses avant d’utiliser un théorème.

10. Recherche du chemin minimal et vérification finale

Un certificat de Bézout vérifie la compatibilité arithmétique, mais ne remplace pas le contrôle de capacité et ne garantit pas que ses coefficients se traduisent directement par le chemin le plus court. Pour trouver ce chemin, construisons le graphe orienté des états : chaque état est un sommet et chaque action autorisée est un arc. Avec deux cruches, il existe au plus (a+1)(b+1) paires ; un parcours en largeur, ou BFS, termine donc toujours.

file ← [(0,0)]
visités ← {(0,0)}

tant que la file n’est pas vide :
    état ← retirer le premier
    si état vaut (d,0) ou (0,d) : reconstruire le chemin
    générer : remplir A, remplir B, vider A, vider B,
              verser A→B, verser B→A
    pour chaque état généré absent de visités :
        l’ajouter à visités
        l’ajouter à la file et mémoriser son prédécesseur

La BFS visite d’abord les chemins comportant le moins d’arcs : le premier chemin qui atteint l’objectif utilise le nombre minimal d’actions selon les règles énoncées. Pour le système fermé 8–5–3, l’état initial, le nombre de coordonnées, le test de l’objectif et le générateur changent : on part de (8,0,0), on cherche (4,4,0) et l’on génère uniquement les transvasements entre chaque paire de récipients.

Liste de vérification

1. Préciser l’ordre des coordonnées et contrôler les capacités dans chaque état.
2. Vérifier que chaque transvasement finit avec une source vide ou une destination pleine.
3. Calculer le PGCD et vérifier qu’il divise l’objectif.
4. Contrôler d ≤ max(a,b) dans le modèle ouvert avec objectif dans une cruche.
5. Ne pas confondre coefficients négatifs et eau négative.
6. Ne pas confondre certificat de Bézout et succession des actions.
7. Si ax+by=d est le bilan final, vérifier que l’autre cruche est vide.
8. Si la source, l’évacuation ou le nombre de récipients change, redéfinir l’espace des états.

Trois contrôles rapides

• Avec 6 et 10 litres, mesurer 5 est impossible car 2 ne divise pas 5.
• Avec 3 et 5 litres, 7 est une combinaison entière, mais ne tient dans aucune cruche : la condition de capacité n’est pas satisfaite.
• Avec 4 et 6 litres, mesurer 2 est possible et le chemin présenté finit bien avec l’autre cruche vide.

Le problème des cruches distingue admirablement les rôles de plusieurs outils : l’invariant évite les recherches inutiles, Bézout certifie la compatibilité arithmétique et le graphe des états, avec les contraintes physiques, transforme ce certificat en une procédure concrète, vérifiable et optimisable.

---

Article préparé par Salvatore Mosaico.