Notre point de départ est Problem Solving Through Recreational Mathematics de Bonnie Averbach et Orin Chein, en particulier la page 118 de l’édition présentée ici. Les auteurs relient le problème des cruches aux équations diophantiennes en donnant aux coefficients un sens concret : les remplissages moins les vidages vers l’extérieur. Nous reprenons cette méthode, l’appliquons à des cruches de 5 et 3 litres pour en obtenir 4 et la formalisons en une procédure exécutable. La visualisation interactive et l’extension par cycles sont des développements pédagogiques de cette page, non des citations du livre.
Ouvrir le laboratoire des cruches, un mouvement à la fois.
1. D’abord les règles : que signifie mesurer 4 litres ?
Nous disposons d’une source, d’une évacuation et de deux cruches sans graduations. Pour la méthode de comptage du livre, nous autorisons : remplir une cruche vide, vider une cruche pleine dans l’évacuation, ou transvaser jusqu’à ce que la cruche source soit vide ou la destination pleine. Aucun arrêt à vue. Le laboratoire applique exactement ces règles.
L’objectif est de laisser la quantité demandée dans une seule cruche, l’autre étant vide. Dire seulement « 4 litres dans la grande cruche » pourrait laisser de l’eau dans la petite : c’est un autre problème. Remplir ou vider des cruches partiellement pleines, permis dans d’autres versions, ne peut pas se compter simplement comme l’apport d’une capacité entière.
2. Le problème du livre : 3 et 5 pour obtenir 1
Le livre exprime cet exemple en gallons. Nous reprenons le même schéma numérique en litres : ce n’est pas une conversion d’unités, mais un problème aux capacités proportionnelles et à la même procédure.
Dans ce premier exemple, A contient 3 litres et B en contient 5. Écrivons 3x + 5y = 1. Le livre propose (x,y) = (2,-1) : prélever deux cruches de 3 et restituer une cruche de 5. Les transvasements rendent possible l’ordre des opérations.
| Étape | Opération | État (A, B) | x | y | Bilan total |
|---|---|---|---|---|---|
| 0 | Départ : les deux cruches sont vides | (0,0) | 0 | 0 | 3 × (0) + 5 × (0) = 0 |
| 1 | Remplir A à la source : 3 L | (3,0) | 1 | 0 | 3 × (1) + 5 × (0) = 3 |
| 2 | Transvaser de A vers B : 3 L | (0,3) | 1 | 0 | 3 × (1) + 5 × (0) = 3 |
| 3 | Remplir A à la source : 3 L | (3,3) | 2 | 0 | 3 × (2) + 5 × (0) = 6 |
| 4 | Transvaser de A vers B : 2 L | (1,5) | 2 | 0 | 3 × (2) + 5 × (0) = 6 |
| 5 | Vider B dans l’évacuation : 5 L | (1,0) | 2 | -1 | 3 × (2) + 5 × (-1) = 1 |
Ici, x augmente seulement lorsque nous prélevons 3 litres à la source ; y diminue seulement lorsque nous évacuons 5 litres. Verser A dans B n’est pas vider A dans l’évacuation : ni x ni y ne change. À la fin, 3 × 2 + 5 × (-1) = 1.
3. États et coefficients : deux registres différents
Désormais, nous utilisons A = 5 litres et B = 3 litres. L’état (u,v) décrit leurs contenus réels. En revanche, x = remplissages de A - vidages de A dans l’évacuation et y = remplissages de B - vidages de B dans l’évacuation. Les deux cruches sont toujours vides au départ.
À chaque étape, 5x + 3y = u + v : l’eau prélevée moins l’eau restituée égale l’eau restante. Un transvasement modifie u et v, mais pas x et y. Un coefficient négatif ne signifie pas de l’eau négative : il compte davantage de vidages que de remplissages de cette cruche.
Pour obtenir (4,0), le bilan final doit donc être 5x + 3y = 4. L’équation seule ne précise ni l’ordre des mouvements ni la cruche contenant l’eau.
4. De l’équation à la famille des solutions
5 = 1 × 3 + 2 et 3 = 1 × 2 + 1, donc PGCD(5,3) = 1. En remontant : 1 = 2 × 3 - 5. Multiplions par 4 : 4 = 8 × 3 - 4 × 5, d’où la solution particulière (-4,8).
Toutes les solutions entières sont x = -4 + 3k et y = 8 - 5k, avec k ∈ ℤ. Pour k = 1, nous obtenons (-1,3) ; pour k = 2, (2,-2). Traduisons les deux sans considérer les coefficients comme une liste de mouvements déjà ordonnée.
Approfondir la méthode générale
La méthode générale des équations diophantiennes, avec théorie et exemple · Laboratoire général de ax + by = c.
5. Trois remplissages de la petite, un vidage de la grande
La solution (x,y) = (-1,3) exprime 4 = -5 + 3 × 3. La cruche B de 3 litres alimente les transvasements ; A, de 5 litres, reçoit l’eau. Nous vidons A lorsqu’elle est pleine et remplissons B à la source lorsqu’elle est vide.
| Étape | Opération | État (A, B) | x | y | Bilan total |
|---|---|---|---|---|---|
| 0 | Départ : les deux cruches sont vides | (0,0) | 0 | 0 | 5 × (0) + 3 × (0) = 0 |
| 1 | Remplir B à la source : 3 L | (0,3) | 0 | 1 | 5 × (0) + 3 × (1) = 3 |
| 2 | Transvaser de B vers A : 3 L | (3,0) | 0 | 1 | 5 × (0) + 3 × (1) = 3 |
| 3 | Remplir B à la source : 3 L | (3,3) | 0 | 2 | 5 × (0) + 3 × (2) = 6 |
| 4 | Transvaser de B vers A : 2 L | (5,1) | 0 | 2 | 5 × (0) + 3 × (2) = 6 |
| 5 | Vider A dans l’évacuation : 5 L | (0,1) | -1 | 2 | 5 × (-1) + 3 × (2) = 1 |
| 6 | Transvaser de B vers A : 1 L | (1,0) | -1 | 2 | 5 × (-1) + 3 × (2) = 1 |
| 7 | Remplir B à la source : 3 L | (1,3) | -1 | 3 | 5 × (-1) + 3 × (3) = 4 |
| 8 | Transvaser de B vers A : 3 L | (4,0) | -1 | 3 | 5 × (-1) + 3 × (3) = 4 |
Il faut 8 mouvements : trois remplissages de B, un vidage de A et quatre transvasements. À (1,3), nous avons déjà 4 litres au total, mais répartis : le dernier transvasement est nécessaire pour obtenir (4,0).
6. Deux remplissages de la grande, deux vidages de la petite
La solution (x,y) = (2,-2) exprime 4 = 2 × 5 - 2 × 3. Cette fois, nous remplissons A et versons vers B, que nous vidons lorsqu’elle est pleine.
| Étape | Opération | État (A, B) | x | y | Bilan total |
|---|---|---|---|---|---|
| 0 | Départ : les deux cruches sont vides | (0,0) | 0 | 0 | 5 × (0) + 3 × (0) = 0 |
| 1 | Remplir A à la source : 5 L | (5,0) | 1 | 0 | 5 × (1) + 3 × (0) = 5 |
| 2 | Transvaser de A vers B : 3 L | (2,3) | 1 | 0 | 5 × (1) + 3 × (0) = 5 |
| 3 | Vider B dans l’évacuation : 3 L | (2,0) | 1 | -1 | 5 × (1) + 3 × (-1) = 2 |
| 4 | Transvaser de A vers B : 2 L | (0,2) | 1 | -1 | 5 × (1) + 3 × (-1) = 2 |
| 5 | Remplir A à la source : 5 L | (5,2) | 2 | -1 | 5 × (2) + 3 × (-1) = 7 |
| 6 | Transvaser de A vers B : 1 L | (4,3) | 2 | -1 | 5 × (2) + 3 × (-1) = 7 |
| 7 | Vider B dans l’évacuation : 3 L | (4,0) | 2 | -2 | 5 × (2) + 3 × (-2) = 4 |
Ce parcours demande 7 mouvements. À l’étape 6, l’état est (4,3) : la grande contient la quantité demandée, mais le bilan reste 5 × 2 + 3 × (-1) = 7. C’est seulement après le vidage de B que nous atteignons (4,0) et la solution (2,-2).
7. Une procédure systématique, pas une suite d’essais
Nous formalisons l’interprétation du livre en un algorithme opérationnel. Choisis une direction, par exemple A → B, et pars de (0,0) :
- Si une cruche contient l’objectif et l’autre est vide, termine.
- Si l’une contient l’objectif et l’autre est pleine, vide celle qui est pleine et termine.
- Sinon, si B est pleine, vide-la.
- Si A est vide, remplis-la à la source.
- Dans les autres cas, transvase
min(u, b - v)litres de A vers B, puis recommence.
La direction B → A échange les rôles. Chaque mouvement est imposé par l’état, pas par une intuition. Nous vérifions d’abord le PGCD et la capacité : si l’objectif est admissible, la procédure l’atteint. Les restes successifs parcourent les multiples du PGCD ; les capacités divisées par le PGCD sont premières entre elles.
Le laboratoire montre les deux directions et leurs comptages effectifs. Ce sont des parcours constructifs : nous n’attribuons au livre ni notre interface ni une recherche automatique du minimum.
8. Les autres solutions entières : ajouter des cycles à bilan nul
La famille est infinie, mais les états des cruches sont en nombre fini : les solutions plus éloignées peuvent comporter des répétitions. Un cycle de (0,0) à (0,0), remplissant B et vidant A, prélève cinq fois 3 litres et restitue trois fois 5 litres. Son apport est (Δx,Δy) = (-3,5) et 5 × (-3) + 3 × 5 = 0.
Effectuer ce cycle puis le parcours de (-1,3) donne (-4,8) : la même eau finale, davantage d’opérations. Le cycle opposé apporte (3,-5). En général, les incréments sont (b/g,-a/g) ou leur opposé, avec g = PGCD(a,b).
Choisis k dans le laboratoire : il construit un parcours avec exactement ces coefficients, en ajoutant le nombre nécessaire de cycles fermés avant le parcours final. La lecture est limitée à 2 000 mouvements pour rester lisible ; une limite d’affichage n’est pas une impossibilité mathématique.
9. Quand c’est possible, quand ça ne l’est pas
Pour des capacités entières positives a et b et un objectif c, isoler c litres est possible exactement si PGCD(a,b) ∣ c et 0 ≤ c ≤ max(a,b), avec source et évacuation. La divisibilité concerne l’équation ; la borne concerne le récipient final. Si c = 0, ne fais rien.
4x + 6y = 1: impossible, car le PGCD est 2 et ne divise pas 1.- Avec 4 et 6, obtenir 2 est possible :
(0,0) → (0,6) → (4,2) → (0,2). - Avec 5 et 3, l’équation pour 8 admet des solutions entières, mais aucune cruche ne contient 8 litres seule.
- Avec 6 et 10, obtenir 8 :
(0,0) → (0,10) → (6,4) → (0,4) → (4,0) → (4,10) → (6,8) → (0,8). Bilan :2 × 10 - 2 × 6 = 8. - Avec 2 et 7, obtenir 1 :
(0,0) → (0,7) → (2,5) → (0,5) → (2,3) → (0,3) → (2,1) → (0,1). - Avec 6 et 9, obtenir 4 est impossible : le PGCD est 3.
Chaque suite suit l’ordre des capacités qui viennent d’être indiquées. Dans le laboratoire, A et B restent fixes, même si A est la plus petite cruche.
10. Une solution correcte n’est pas forcément la plus courte
Pour 5 et 3, le parcours de 7 mouvements est plus court que celui de 8. Minimiser |x| + |y| ne suffit pas : cette somme vaut 4 pour les deux couples, mais le nombre de transvasements diffère. Si l’autre cruche peut rester pleine, 6 mouvements suffisent : c’est un autre objectif.
Pour certifier le minimum, on peut utiliser un parcours en largeur (BFS) du graphe des états, en comptant chaque remplissage, vidage ou transvasement comme un mouvement. Cette vérification algorithmique est distincte du comptage. Le laboratoire indique la longueur des parcours affichés sans les qualifier automatiquement d’optimaux.
11. La variante fermée 8–5–3 est un autre modèle
Si le récipient de 8 commence plein, sans source ni évacuation, il ne reste que les transvasements. Pour partager les 8 litres en deux parts de 4, avec les états dans l’ordre (8,5,3), voici un parcours :
(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 reste toujours 8 : l’interprétation des prélèvements et évacuations du modèle ouvert ne peut pas être transférée sans adaptation. Le nouveau laboratoire concerne deux cruches avec source et évacuation.
12. Lire les deux barres du laboratoire
Les deux barres partagent la même échelle en litres : la cruche de 5 est plus haute que celle de 3. Le contour représente la capacité ; l’eau colorée indique le contenu actuel. En dessous figurent l’état, x et y, l’eau prélevée et l’eau évacuée. Le bilan est vérifié à chaque mouvement.
Appuie sur Suivant pour une opération, Précédent pour la revoir, ou lance la lecture automatique à un mouvement par seconde. Change de direction, choisis k ou reviens au début. Le tableau contient tout le parcours et distingue les cycles de la partie finale.
L’idée à retenir est simple : l’équation dit combien ; la procédure construit comment ; les états vérifient que chaque mouvement est autorisé.