Deux sabliers, aucune horloge et une durée à mesurer : suffit-il d’ajouter et de soustraire leurs durées ? Le lien avec le problème des cruches et les équations diophantiennes est naturel, mais une identité numérique n’est pas une suite de gestes physiquement réalisables.
La méthode générale, expliquée pas à pas
Pour comprendre quand ax + by = c admet des solutions entières, comment trouver l’identité de Bézout et comment obtenir toutes les solutions, lis Équations diophantiennes linéaires : théorie et exemple avec Euclide étendu.
Ouvrir le laboratoire général des équations diophantiennes: saisis les trois coefficients entiers a, b et c, puis suis les divisions, les substitutions et les contraintes sans sauter d’étapes.
Nous conservons ici les problèmes et les protocoles des sabliers : l’équation certifie la compatibilité arithmétique, mais ne remplace pas la vérification des retournements et de l’instant où commence la mesure.
Ouvrir le laboratoire des sabliers : choisissez a, b et d ; observez Euclide étendu, la preuve d’existence ou d’impossibilité, toutes les solutions entières et un protocole visuel de retournements.
1. Règles : mesurer dès le départ ou après préparation
Les sabliers sont idéaux, de durées entières a et b, et contiennent initialement tout leur sable en bas. Au départ, vous pouvez en lancer un ou les deux. Ensuite, intervenez uniquement lorsqu’au moins un se vide : retournez-en un, les deux ou aucun. On peut retourner celui qui coule encore. Il est interdit d’estimer le sable à vue ou d’utiliser une autre horloge.
Si un sablier de durée a a encore r minutes à écouler, après retournement il lui reste a − r minutes. Par exemple, un sablier de 7 minutes ayant coulé pendant 1 minute a r = 6 ; le retourner laisse 7 − 6 = 1 minute. Ce geste doit toutefois avoir lieu à un instant reconnaissable grâce à un vidage.
- Mesure dès le départ : partir à t = 0 et obtenir un signal exactement à t = d.
- Mesure après préparation : préparer le système, commencer la mesure à un vidage et terminer à un autre vidage d minutes plus tard.
Ce sont deux demandes différentes. Avec des sabliers de 3 et 5 minutes, on ne peut signaler 1 minute après le départ : le premier événement ne peut précéder 3 minutes. Mais on peut mesurer 1 minute plus tard, par exemple entre 9 et 10 minutes, avec trois cycles de 3 et deux cycles de 5.
2. Le filtre mathématique : le PGCD doit diviser d
Cherchons des entiers x et y tels que ax + by = d. Les entiers comprennent les nombres positifs, zéro et les nombres négatifs. Si g = PGCD(a,b), tout ax + by est multiple de g, puisque a et b le sont. Si g ne divise pas d, l’équation est donc impossible.
La réciproque est vraie aussi. L’identité de Bézout donne des entiers u et v tels que au + bv = g. Si d = gh, multiplions par h : a(uh) + b(vh) = d. Ainsi ax + by = d possède des solutions entières si et seulement si PGCD(a,b) divise d.
Pour les sabliers, tous les instants observables et tous les temps restants demeurent multiples de g : c’est vrai initialement, puis préservé par soustraction et retournement. Si g ne divise pas d, l’intervalle est impossible même avec préparation.
Si g divise d, on peut toujours mesurer l’intervalle en autorisant une préparation : choisissons une solution de signes opposés et lisons d comme la différence entre deux instants de fin de cycles complets. On lance les deux décomptes ensemble, on relance chaque sablier à ses vidages jusqu’au nombre de cycles fixé, et on mesure entre leurs deux vidages finaux. Le critère seul ne garantit pas une mesure commençant dès t = 0.
3. Euclide étendu : de 4 et 7 à une solution de 4x + 7y = 9
Trouvons d’abord le PGCD par divisions avec reste :
7 = 1 × 4 + 34 = 1 × 3 + 13 = 3 × 1 + 0
Le dernier reste non nul vaut 1. Remontons : 1 = 4 − 3 = 4 − (7 − 4) = 2 × 4 − 7. Donc u = 2 et v = −1. Puisque 9 = 9 × 1, multiplions par 9 : 9 = 18 × 4 − 9 × 7. Une solution est (x₀,y₀) = (18,−9).
Le laboratoire exprime aussi chaque reste comme combinaison de a et b : c’est la même remontée de Bézout, conservée pendant le calcul. Pour le cas impossible 6x + 10y = 7, il trouve g = 2 et écrit 7 = 3 × 2 + 1 : le reste 1 prouve l’absence de solution.
4. Pas un seul couple : toutes les solutions
À partir d’une solution (x₀,y₀), toutes les autres sont x = x₀ + (b/g)k et y = y₀ − (a/g)k, avec k entier. Les termes ajoutés s’annulent : a(b/g)k − b(a/g)k = 0. Réciproquement, soustraire deux solutions et utiliser que a/g et b/g sont premiers entre eux donne exactement cette famille.
Ici x = 18 + 7k et y = −9 − 4k. Avec k = −2 on obtient (4,−1) : 4 × 4 − 7 = 9. Avec k = −3 on obtient (−3,3) : −3 × 4 + 3 × 7 = 9. Les deux conviennent.
Un coefficient négatif indique une différence de durées, pas un temps négatif ni un nombre négatif de retournements. Pour simplement enchaîner des cycles complets, imposons x ≥ 0 et y ≥ 0, soit ceil(−x₀/(b/g)) ≤ k ≤ floor(y₀/(a/g)) : ceil arrondit à l’entier supérieur, floor à l’inférieur. Pour 4x + 7y = 9, aucun couple n’est non négatif. Pourtant, retourner des sabliers partiellement remplis permet de mesurer 9 minutes dès le départ : voir le problème 3. Il ne faut pas confondre ces deux vérifications.
5. Douze problèmes avec solutions expliquées
1. Premier pas : 3 et 5 pour mesurer 8
Avec des sabliers de 3 et 5 minutes, mesurez 8 minutes dès le départ.
Solution
Lancez uniquement le 3. À son vidage, à t = 3, lancez le 5. Il se vide à t = 8. L’équation est 3x + 5y = 8 avec x = y = 1 : les cycles s’ajoutent successivement.
Essayer 3, 5 → 8 au laboratoire
2. La différence : 4 et 7 pour mesurer 3
Mesurez un intervalle de 3 minutes avec des sabliers de 4 et 7. La préparation est autorisée.
Solution
Lancez les deux ensemble. Commencez la mesure à t = 4 et terminez à t = 7. La durée est 7 − 4 = 3, donc (x,y) = (−1,1). Ce ne sont pas 3 minutes dès le départ : le premier événement n’arrive qu’à t = 4.
Essayer 4, 7 → 3 au laboratoire
3. Un retournement partiel : 4 et 7 pour mesurer 9
Mesurez 9 minutes dès le départ avec des sabliers de 4 et 7.
Solution
- À t = 0, lancez les deux.
- À t = 4, retournez le 4.
- À t = 7, retournez le 7 ; le 4 continue avec 1 minute restante.
- À t = 8, le 4 se vide. Le 7 a coulé pendant 1 minute : retournez-le, il reste 1 minute.
- À t = 9, le 7 se vide : fin.
4 × 4 − 7 = 9 certifie la compatibilité arithmétique sans décrire ces gestes. Le protocole physique se vérifie séparément.
Essayer 4, 7 → 9 au laboratoire
4. Un autre retournement partiel : 7 et 11 pour mesurer 15
Mesurez 15 minutes dès le départ avec des sabliers de 7 et 11.
Solution
Lancez les deux. À t = 7, retournez le 7. À t = 11, le 11 se vide et il reste 3 minutes dans le 7. Retournez le 7 : il reste maintenant 7 − 3 = 4 minutes. Il se videra à t = 15. L’identité −7 + 2 × 11 = 15 résout l’équation.
Essayer 7, 11 → 15 au laboratoire
5. PGCD supérieur à 1 : 6 et 10 pour mesurer 4
Mesurez 4 minutes avec des sabliers de 6 et 10, avec préparation autorisée.
Solution
PGCD(6,10) = 2 et 2 divise 4. Lancez les deux et mesurez de t = 6 à t = 10. L’identité est −6 + 10 = 4. Les durées n’ont pas à être premières entre elles : leur PGCD doit diviser l’objectif.
Essayer 6, 10 → 4 au laboratoire
6. Une vraie impossibilité : 6 et 10 pour mesurer 7
Peut-on mesurer 7 minutes, même après préparation, avec des sabliers de 6 et 10 ?
Solution
Non. 6x + 10y = 2(3x + 5y) est toujours pair, alors que 7 est impair. Tous les vidages observables restent à des instants pairs ; leur différence est aussi paire. Aucun geste plus astucieux ne peut changer cela.
Vérifier cette impossibilité au laboratoire
7. Une seule minute : 5 et 8
Mesurez un intervalle de 1 minute avec des sabliers de 5 et 8. Vous pouvez les préparer avant.
Solution
−3 × 5 + 2 × 8 = 1. Lancez les deux. Relancez le 5 à t = 5 et t = 10, puis le 8 à t = 8. À t = 15, le 5 termine son troisième cycle : commencez la mesure. À t = 16, le 8 termine son deuxième : fin. Vous mesurez de 15 à 16, pas 1 minute après le départ.
Essayer 5, 8 → 1 au laboratoire
8. Cycles complets : 8 et 12 pour mesurer 20
Mesurez 20 minutes dès le départ avec des sabliers de 8 et 12.
Solution
8 + 12 = 20. Lancez le 8 et, à son vidage à t = 8, lancez le 12. Il termine à t = 20. PGCD(8,12) = 4 divise 20 ; (x,y) = (1,1).
Essayer 8, 12 → 20 au laboratoire
9. Un reste qui bloque tout : 8 et 12 pour mesurer 10
Peut-on mesurer 10 minutes avec des sabliers de 8 et 12, même après préparation ?
Solution
Non. Le PGCD est 4, mais 10 = 2 × 4 + 2. Tout 8x + 12y est multiple de 4 ; 10 ne l’est pas. Tous les événements et leurs différences restent multiples de 4.
Vérifier 8, 12 → 10 au laboratoire
10. Des durées plus grandes : 9 et 14 pour mesurer 23
Mesurez 23 minutes dès le départ avec des sabliers de 9 et 14.
Solution
Lancez le 9. À son vidage, lancez le 14. Il finit à t = 9 + 14 = 23. Le couple (1,1) résout 9x + 14y = 23.
Essayer 9, 14 → 23 au laboratoire
11. Mêmes sabliers, autre objectif : 9 et 14 pour mesurer 5
Mesurez 5 minutes avec les mêmes sabliers. La préparation est autorisée.
Solution
Lancez les deux. Commencez à la fin du 9, à t = 9, et terminez à la fin du 14, à t = 14. L’identité est −9 + 14 = 5. Le protocole change avec l’objectif, même si les sabliers restent les mêmes.
Essayer 9, 14 → 5 au laboratoire
12. Une unité de temps plus grande : 10 et 15 pour mesurer 5
Mesurez 5 minutes avec des sabliers de 10 et 15, avec préparation autorisée. Pourriez-vous mesurer 1 minute ?
Solution
Lancez les deux et mesurez de t = 10 à t = 15 : −10 + 15 = 5. Le PGCD vaut 5, donc 5 est possible mais pas 1. L’unité arithmétique accessible n’est pas toujours une minute : ici elle vaut 5 minutes.
Essayer 10, 15 → 5 au laboratoire
6. Lire le laboratoire
Le calcul sépare deux tâches. Il résout d’abord l’équation : divisions d’Euclide, identité de Bézout, multiplication par d/g, famille paramétrique et contrôle des coefficients non négatifs. Modifier k permet de vérifier d’autres couples sans changer ax + by.
Il cherche ensuite dans les états (t,rA,rB), où rA et rB sont les minutes restantes. À chaque vidage, il examine les quatre gestes autorisés et attend l’événement suivant : ni instant sauté ni horloge cachée. Il explore tous les états accessibles jusqu’à t = d. S’il trouve un signal à d, il montre une mesure dès le départ ; sinon, si le PGCD divise d, il construit une mesure après préparation en comparant des cycles complets. Il ne garantit ni le minimum de gestes ni la préparation la plus courte.
Les commandes avancent événement par événement, lancent la lecture, mettent en pause ou reviennent au départ. Le sable affiché est celui après le geste ; le tableau indique instant, événement, retournement et temps restants. Pour les mesures préparées, le début du chronomètre logique est signalé : le temps de préparation ne doit pas être confondu avec l’intervalle demandé.
Pour approfondir le théorème utilisé : Raji, Elementary Number Theory, équations diophantiennes linéaires. Ces problèmes et explications développent ce critère dans le modèle des sabliers.