Encore une histoire de bidons

yoshi · 20-06-2026 18:22:20

B'soir;

Vous disposez de 3 bidons, chacun contenant un nombre entier de litres d'eau.
On peut diminuer le contenu d'un bidon en doublant le contenu d'un autre moins rempli :
si $n_1 ≤n_2$ on passe à $2\times n_1$, avec $n_2$ ne contenant plus alors que $n_2-n_1$...
On admettra que chaque bidon est assez grand pour contenir toute l'eau mise en jeu.

Trouver un algorithme pour vider l'un des bidons au bout d'un nombre fini d'opérations.

@+

syrac · 21-06-2026 01:14:43

Bonsoir,

Si on considère que les trois bidons contiennent au total 9 L, par exemple (3, 3, 3), (1, 3, 5), ..., il suffit d'ouvrir Mathematica et de faire

Tuples[Range[8], 3] // Select[Total[#] == 9 &]

Ce qui donne

(1, 1, 7), (1, 2, 6), (1, 3, 5), (1, 4, 4), (1, 5, 3), (1, 6, 2), (1, 7, 1), (2, 1, 6), (2, 2, 5), (2, 3, 4), (2, 4, 3), (2, 5, 2), (2, 6, 1), (3, 1, 5), (3, 2, 4), (3, 3, 3), (3, 4, 2), (3, 5, 1), (4, 1, 4), (4, 2, 3), (4, 3, 2), (4, 4, 1), (5, 1, 3), (5, 2, 2), (5, 3, 1), (6, 1, 2), (6, 2, 1), (7, 1, 1)

Tous les triplets en gras (possèdent deux termes égaux) contiendront un 0 à l'étape suivante, c'est-à-dire un bidon vide. Par exemple, (2, 5, 2) → (4, 5, 0) = une opération.

yoshi · 21-06-2026 10:33:31

Bonjour,

Bon...
Et quel est donc l'algorithme demandé ?
Ça : Tuples[Range[8], 3] // Select[Total[#] == 9 &] ?
Et quel est donc l'algorithme employé par Mathematica ?
Et si tu te passais de Mathematica, tu ferais comment ?

Je l'avais fait via Python il y a déjà 13 ans en n'employant que les instructions "basiques" et ça m'avait pris une douzaine de lignes et pas mal de réflexion pour corriger les bugs : doublons, nombres parfois négatifs, bouclage sans fin...

Il faudrait que je me repenche dessus pour le refaire...

En tout état de cause et en l'état actuel :

Sorties du prog Python a écrit :

Contenances de départ : [1, 1, 2]
[2, 1, 1]
[2, 0, 2]
Autre demande faite :
Contenances de départ : [54, 78, 37]
[37, 54, 78]
[74, 17, 78]
[17, 74, 78]
[34, 74, 61]
[68, 74, 27]
[136, 6, 27]
[6, 27, 136]
[12, 27, 130]
[24, 27, 118]
[48, 3, 118]
[3, 48, 118]
[6, 48, 115]
[12, 48, 109]
[24, 48, 97]
[48, 48, 73]
[96, 0, 73

J'avais pris le parti
- de faire un tri croissant dès le départ
- de refaire un tri croissant après chaque transfert...

Ce qui me gêne, c'est qu'il n'offre pas toujours la solution la plus courte : c'est à ça que je voudrais remédier...

Dernière modification par yoshi (21-06-2026 14:17:43)

syrac · 21-06-2026 13:03:11

J'ai bien entendu posé la question à ChatGPT. Il a pondu un algorithme fonctionnel d'une quarantaine de lignes, a admis qu'un algo d'une douzaine de lignes était plausible — sans toutefois s'y coller — et s'est ensuite orienté vers la recherche d'une solution symbolique sans toutefois aboutir. Voici ce qu'il propose pour commencer :

$a,b,c \in \mathbb{N}_1 \qquad a \le b \le c \qquad a+b+c=C$ (constante)

puis de poser

$(a,b,c) \longrightarrow (a,2b,c−b)$

Il préconise d'opérer un tri ascendant de chaque nouveau résultat pour conserver le schéma de départ, jusqu'à l'apparition d'un zéro. Mais immédiatement après il trouve un contre-exemple :

$(1,1,2) \rightarrow (1,2,1) \rightarrow tri \rightarrow (1,1,2) \longrightarrow $ boucle infinie.

Son verdict : il faut ajouter une règle de choix plus subtile, ou bien utiliser une recherche avec mémoire. Il faut tout lui arracher...

yoshi · 21-06-2026 14:39:40

Salut,

Euh... une douzaine de lignes avais-je dit ? J'étais optimiste, je suis bien plus près de la trentaine que de la douzaine, mais le code n'est pas vraiment optimisé : il y a 13 ans, j'étais moins avancé qu'aujourd'hui...
Et en dehors de cette IA, d'autres sont accessibles (Gemini par ex) ? Histoire de comparer...

Le tri ascendant, c'est bien ce que j'avais fait...
Mais la boucle sans fin, j'étais tombé dessus et avais résolu de façon simple le problème et ça n'arrive plus...
Un simple test : si n1=n2 ou n2=n3 alors faire la soustraction et le test d'arrêt intégré empêche ensuite de boucler sans fin...
@+

syrac · 21-06-2026 16:14:21

J'ai posé la question à Qwen. Je suis toujours ébahi par sa concision. Il va droit au but tandis que ChatGPT est très verbeux sans être toujours très pertinent. Je fournis l'algo de Qwen, qui n'est pas plus court que celui de ChatGPT mais plus facile à lire :

from collections import deque

def vider_bidon(a, b, c):

    # 1. État initial trié

    start = tuple(sorted((a, b, c)))

    # Si c'est déjà vide, on a fini

    if start[0] == 0:

        return [start]

    # 2. Initialisation du BFS

    queue = deque([start])

    came_from = {start: None}  # Pour reconstruire le chemin à la fin

    while queue:

        x, y, z = queue.popleft()

        # 3. Génération des 3 seuls mouvements possibles (grâce au tri)

        moves = [

            (2*x, y-x, z),  # x vers y

            (2*x, y, z-x),  # x vers z

            (x, 2*y, z-y)   # y vers z

        ]

        for move in moves:

            # On trie le nouvel état pour profiter de la symétrie

            nxt = tuple(sorted(move))

            if nxt not in came_from:

                came_from[nxt] = (x, y, z)

                # 4. Condition d'arrêt (le plus petit est à l'indice 0 grâce au tri)

                if nxt[0] == 0:

                    # Reconstruction du chemin à l'envers

                    path = [nxt]

                    curr = nxt

                    while came_from[curr] is not None:

                        curr = came_from[curr]

                        path.append(curr)

                    return path[::-1]  # On remet dans l'ordre chronologique

                queue.append(nxt)

    return None

# --- Test ---

if __name__ == "__main__":

    chemin = vider_bidon(123, 456, 789)

    print(f"Solution trouvée en {len(chemin) - 1} étapes :\n")

    for i, etape in enumerate(chemin):

        print(f"Étape {i} : {etape}")

Solution trouvée en 9 étapes :

Étape 0 : (123, 456, 789)
Étape 1 : (246, 333, 789)
Étape 2 : (87, 492, 789)
Étape 3 : (174, 405, 789)
Étape 4 : (174, 384, 810)
Étape 5 : (174, 426, 768)
Étape 6 : (174, 342, 852)
Étape 7 : (174, 510, 684)
Étape 8 : (348, 510, 510)
Étape 9 : (0, 348, 1020)

EDIT : signification de l'acronyme 'BFS' : https://fr.wikipedia.org/wiki/Algorithm … en_largeur

Dernière modification par syrac (21-06-2026 16:24:13)

syrac · 21-06-2026 16:31:28

[suite du précédent]

Je reprends l'exemple de Yoshi plus haut : (a, b, c) = (54, 78, 37). Résultat avec l'algo de Qwen :

Étape 0 : (37, 54, 78)
Étape 1 : (17, 74, 78)
Étape 2 : (34, 57, 78)
Étape 3 : (44, 57, 68)
Étape 4 : (11, 44, 114)
Étape 5 : (22, 44, 103)
Étape 6 : (44, 44, 81)
Étape 7 : (0, 81, 88)

On comprend mieux pourquoi la quasi-totalité des développeurs utilisent les capacités incomparables des IA en matière de codage. Pourquoi se creuser la tête puisqu'elles font mieux que nous, et surtout beaucoup plus rapidement ? Par contre, il ne faut pas compter sur elles pour développer un projet de A à Z, et la raison en est qu'elles n'ont aucune initiative, ou rarement. Il faudra toujours un humain pour donner son orientation au projet, pour décider de ce qu'on fait à la prochaine étape ou de ce que à quoi on renonce.

Avant novembre 2022, développer une application consistait à passer la majeure partie du temps à chercher une solution sur Internet, et notamment Stack Overflow, que ce soit du code fonctionnel ou une solution à un problème qu'on ne parvenait pas à résoudre. Aujourd'hui, dès qu'on a besoin de coder quelque chose ou résoudre un problème difficile on ne fait ni une ni deux, on demande à l'IA de s'en charger. ChatGPT appelle ça "déléguer le boulot à l'IA", et il trouve que c'est très malin. Encore une compétence humaine en voie de disparition...

Dernière modification par syrac (21-06-2026 16:52:58)

Michel Coste · 21-06-2026 18:25:01

Bonsoir,
Ce que j'aimerais voir, c'est une démonstration du fait qu'il y a toujours une solution.

syrac · 21-06-2026 21:18:06

Question de la démonstration posée par Michel Coste. Réponse de Qwen. La mise en page n'est pas terrible puisqu'il s'agit d'une exportation de ladite réponse au format texte. Heureusement, le code LaTeX est préservé :

QWEN

Voici une démonstration claire, rigoureuse mais accessible, basée sur des idées classiques de théorie des nombres et d’invariants.

---

Théorème

> Étant donné trois entiers positifs $ a, b, c \in \mathbb{N}^* $, il existe toujours une suite finie d’opérations autorisées (doubler le plus petit en prélevant sur un plus grand) qui conduit à un état où l’un des bidons est vide.

---

Idée centrale : on peut simuler l’algorithme d’Euclide

L’opération autorisée :
- Si $ x \le y $, alors $ (x, y) \mapsto (2x, y - x) $

peut sembler étrange, mais elle permet en fait de réduire progressivement les différences entre les quantités, tout comme l’algorithme d’Euclide réduit deux nombres via des soustractions successives.

Mais ici, on a trois nombres → ce qui donne assez de flexibilité pour éviter les blocages.

---

Invariant fondamental : le PGCD

Soit $ d = \gcd(a, b, c) $. Alors :

- Toute opération conserve $ d $. En effet, si $ d \mid x $ et $ d \mid y $, alors $ d \mid 2x $ et $ d \mid (y - x) $.
- Donc, tous les états accessibles sont des multiples de $ d $.
- On peut donc diviser tous les nombres par $ d $ dès le départ, sans perte de généralité. Autrement dit, on suppose désormais que $ \gcd(a, b, c) = 1 $.

> ? Objectif équivalent : atteindre un état contenant un 0 et deux entiers dont le PGCD est 1.

---

Stratégie : faire décroître la somme des carrés

Considérons la fonction potentiel suivante :
\[
P(x, y, z) = x^2 + y^2 + z^2
\]

Montrons que chaque opération non triviale diminue strictement cette somme, sauf dans des cas particuliers qu’on peut contourner grâce au troisième bidon.

Calcul :
Supposons $ x \le y $, et on applique $ (x, y) \mapsto (2x, y - x) $. La variation de $ P $ est :
\[
\Delta P = (2x)^2 + (y - x)^2 - (x^2 + y^2)
= 4x^2 + y^2 - 2xy + x^2 - x^2 - y^2
= 4x^2 - 2xy
= 2x(2x - y)
\]

Donc :
- Si $ 2x < y $, alors $ \Delta P < 0 $ → la somme des carrés diminue.
- Si $ 2x = y $, alors $ \Delta P = 0 $, et on obtient $ (2x, y - x) = (y, x) $ → on a juste échangé les valeurs.
- Si $ 2x > y $, alors $ \Delta P > 0 $ → la somme augmente, ce qui semble mauvais.

Mais attention : on n’est pas obligé de choisir cette paire-là !

Grâce au troisième bidon, on peut toujours éviter les coups qui augmentent $ P $, ou les utiliser temporairement pour créer une configuration où un coup utile devient possible.

---

Argument de terminaison par descente infinie

Comme la somme totale $ S = a + b + c $ est constante, l’espace des états possibles est fini : il y a au plus $ (S+1)^2 $ triplets d’entiers non négatifs de somme $ S $.

De plus, tant qu’aucun bidon n’est vide, il existe toujours une opération qui diminue strictement $ P $ ou rapproche deux valeurs, ce qui permet in fine de générer un zéro.

Mais voici une preuve plus élégante, due à une observation combinatoire :

---

Preuve constructive via la représentation binaire

On utilise un résultat connu (appelé parfois lemme des trois verres) :

> Si $ \gcd(a, b, c) = 1 $, alors il existe une suite d’opérations qui produit un bidon contenant 1 litre.

Une fois qu’on a un bidon avec 1, il devient trivial de vider un autre :
- Supposons qu’on ait $ (1, u, v) $ avec $ u, v \ge 1 $.
- Tant que $ u > 1 $, on applique $ (1, u) \mapsto (2, u-1) $, puis on réordonne.
- En répétant cela, on finit par avoir $ (1, 1, w) $, puis $ (2, 0, w) $ → un zéro apparaît.

Donc tout revient à montrer qu’on peut atteindre 1.

Or, l’opération $ (x, y) \mapsto (2x, y - x) $ permet de réaliser des combinaisons linéaires entières du type $ mx + ny $, modulo des puissances de 2. Comme le PGCD est 1, Bézout garantit qu’il existe des entiers $ m, n, p $ tels que $ ma + nb + pc = 1 $. Grâce aux trois bidons, on peut simuler ces combinaisons via une suite d’opérations inversibles (modulo conservation de la somme).

Une version plus formelle montre que l’ensemble des valeurs atteignables dans un bidon est exactement l’ensemble des multiples de $ d = \gcd(a,b,c) $ inférieurs ou égaux à $ S $. Donc si $ d = 1 $, 1 est atteignable.

Et une fois que 1 est atteint, comme vu plus haut, 0 l’est aussi.

---

Conclusion

- L’espace d’états est fini → l’algorithme BFS termine.
- Le PGCD est conservé → on peut supposer $ \gcd = 1 $.
- Sous cette hypothèse, **1 est atteignable**, donc **0 aussi**.
- Donc **quelle que soit la configuration initiale**, **un bidon peut être vidé en un nombre fini d’étapes**.

C’est pourquoi ton algorithme **fonctionne toujours** ! ?

---

Ce problème est une variante du "water jug problem" ou du "three jug problem", et la preuve ci-dessus s’appuie sur des idées classiques en théorie algorithmique des nombres.

Dernière modification par syrac (21-06-2026 21:19:25)

Michel Coste · 21-06-2026 22:36:54

Pour moi, c'est complètement bidon ;)
Juste une suite d'affirmations hasardeuses.

syrac · 22-06-2026 01:15:15

Comme attendu. Les IA qui tentent une démonstration mathématique finissent toujours descendues en flamme. Alternative : ChatGPT Pro à 200 €/mois, sans garantie de résultat. Bref, il faut toujours garder à l'esprit qu'une IA n'est pas consciente et ne sait même pas de quoi elle parle. Mais ça tient à peu de chose : il suffirait qu'elle sorte de l'oubli une démonstration similaire faite il y a quelques décennies par un Terence Tao inconnu pour qu'aussitôt on s'extasie sur "une intelligence en train de dépasser celle de l'Homme".

Dernière modification par syrac (22-06-2026 01:24:37)

Michel Coste · 22-06-2026 08:39:56

J'avais une piste de démonstration, mais qui se casse la figure.
Ça part de l'observation qu' un plus court vecteur entier non nul orthogonal à $(0,n_2,n_3)$ est $(1,0,0)$, de longueur $1$ et que ce fait caractérise les configurations avec un $n_i$ nul. De même, un plus court vecteur entier non nul orthogonal à $(a,a,n_3)$ est $(1,-1,0)$, de longueur $\sqrt2$, et ce fait caractérise les configurations avec deux $n_i$ égaux. L'idée est alors de choisir, à partir d'une configuration donnée, le mouvement qui donne la plus petite longueur d'un plus court vecteur entier non nul orthogonal. Il existe toujours un mouvement qui n'augmente pas la longueur d'un plus court vecteur entier non nul orthogonal (*), mais malheureusement il se peut que l'on ne puisse pas la faire baisser strictement. Si on itère ce procédé, on peut donc boucler : raté !

P.S. (*) En plus ce n'est même pas vrai ! Il se peut que tous les mouvements possibles augmentent la longueur d'un plus court vecteur entier non nul orthogonal.

Dernière modification par Michel Coste (22-06-2026 10:45:09)

syrac · 23-06-2026 01:24:15

Voici la participation de Mistral au format PDF.

Michel Coste · 23-06-2026 09:19:41

Plus explicite que la bouillie de Qwen, mais toujours bidon. On voit que dans le cas où $2a > c$, aucun mouvement autorisé ne fera baisser $M$. Dès le cas 1, la "démonstration" se casse la figure.
Il vaut mieux analyser avec un regard critique les réponses des I.A..

syrac · 23-06-2026 16:46:41

J'ai trouvé une simplification, qui consiste à partir systématiquement de (a, b, 999). L'entier c devient en quelque sorte le "déversoir" du système pour le cas où a ne peut pas être soustrait de b. C'est son unique fonction. Et ce qu'on observe est que c ne croît jamais, au contraire il stagne ou décroît. Donc tout se passe entre a et b. Je reprends l'exemple de Joshi plus haut, toujours avec l'algo de Qwen (je rappelle qu'il effectue un tri ascendant après chaque étape) :

Étape 0 : (54, 78, 999)
Étape 1 : (24, 108, 999)
Étape 2 : (24, 216, 891)
Étape 3 : (48, 192, 891)
Étape 4 : (96, 192, 843)
Étape 5 : (192, 192, 747)
Étape 6 : (0, 384, 747)

Sauf erreur de ma part, le problème trouve une solution très rapidement, car

$2\,a=b-a$ est la condition de l'apparition d'un 0 à l'étape suivante. Or, dans ce cas on a

$a=\dfrac{b}{3}$

Exemple avec $a=3, b=9$ :

Étape 0 : (3, 9, 999)
Étape 1 : (6, 6, 999)
Étape 2 : (0, 12, 999)

Prenons $a=17, b=51$ :

Étape 0 : (17, 51, 999)
Étape 1 : (34, 34, 999)
Étape 2 : (0, 68, 999)

Il existe un entier sur 3 divisible par 3, ce qui fait d'eux la catégorie d'entiers la plus répandue : 3, 6, 9, 12, ... Je suppose que cette caractéristique augmente la probabilité de tomber sur un 0 assez rapidement.

Dernière modification par syrac (23-06-2026 16:57:54)

Michel Coste · 23-06-2026 17:47:34

L'intervention précédente ne représente en aucune façon un progrès vers une démonstration. À quoi sert-elle ?

syrac · 23-06-2026 22:16:35

Je comprends que ce soit obscur pour beaucoup de gens...

syrac · 23-06-2026 23:08:27

... mais sans doute qu'en généralisant on peut améliorer ça. Voici la relation entre $a$ et $b$ qui conduit à l'apparition d'un 0 :

$a=\dfrac{b}{x+1}$

Prenons $b$=35 et $x$=4 :

$a=\dfrac{35}{4+1}=7 \longrightarrow 4\,a = 35-a$

Étape 0 : (7, 35, 999)
Étape 1 : (14, 28, 999)
Étape 2 : (28, 28, 985)
Étape 3 : (0, 56, 985)

Ça fonctionne pour tout $b$ multiple de $x+1$. Je ne parle pas d'une démonstration mais du fait qu'il existe une infinité de possibilités de provoquer une descente rapide vers 0, en choisissant soigneusement $b$ et $x$. Des valeurs de $a$ et $b$ non correlées demanderont plus d'étapes pour parvenir à l'apparition d'un 0, mais à l'une des étapes on trouvera la même relation entre $a$ et $b$. Exemple (on change simplement la valeur de $a$ par rapport à l'exemple précédent) :

Étape 0 : (8, 35, 999)
Étape 1 : (16, 27, 999)
Étape 2 : (11, 32, 999)
Étape 3 : (21, 22, 999)
Étape 4 : (22, 42, 978)
Étape 5 : (20, 44, 978)
Étape 6 : (24, 40, 978)
Étape 7 : (16, 48, 978) ← $b=48, x=2 \qquad \dfrac{48}{x+1}=16 \qquad 2 \times 16=48-16 \longrightarrow 0$ atteint
Étape 8 : (32, 32, 978)
Étape 9 : (0, 64, 978)

On voit que la transformation initiale $2\,a=b-a$ n'est qu'un cas particulier.

Dernière modification par syrac (23-06-2026 23:16:10)

yoshi · 24-06-2026 09:16:24

Bonjour,

@syrac
Je regarderai ta proposition de plus près, tout à l'heure...

@tous
J'ai relu la discussion d'il y a 13 ans...
Celui qui avait proposé le problème s'était essayé - sans succès - à la méthode de "descente infinie de Fermat"...
Ça parle à quelqu'un ?

Je vais aussi aller questionner Google à ce sujet...

@+

[EDIT]
Je cherchais bien loin :
Bibmath --> Descente infinie
Mais là, je n'en vois pas bien (euphémisme) l'utilisation dans le problème...

Dernière modification par yoshi (24-06-2026 10:23:23)

syrac · 24-06-2026 13:04:30

J'ai demandé à Qwen de faire en sorte que le contenu des triplets soit affiché dans l'ordre naturel (a, b, c), parce qu'avec le tri il faut se faire des noeuds au cerveau pour suivre. Il a trouvé une solution élégante : utiliser le tri dans le calcul, pour les performances, mais afficher les étapes dans l'ordre original. Nouvelle version :

from collections import deque

def vider_bidon(a, b, c):

    start = (a, b, c)

    # Si c'est déjà vide

    if 0 in start:

        return [start]

    queue = deque([start])

    came_from = {start: None}

    # On utilise un set de tuples TRIÉS pour éviter les doublons

    # mais on garde l'ordre original dans la queue

    visited = {tuple(sorted(start))}

    while queue:

        x, y, z = queue.popleft()

        # Générer tous les mouvements possibles (6 au max)

        moves = []

        state = [x, y, z]

        for i in range(3):

            for j in range(3):

                if i != j and state[i] <= state[j] and state[i] > 0:

                    new_state = state[:]

                    new_state[i] = 2 * state[i]

                    new_state[j] = state[j] - state[i]

                    moves.append(tuple(new_state))

        for nxt in moves:

            nxt_sorted = tuple(sorted(nxt))

            if nxt_sorted not in visited:

                visited.add(nxt_sorted)

                came_from[nxt] = (x, y, z)

                # Condition d'arrêt

                if 0 in nxt:

                    # Reconstruction du chemin

                    path = [nxt]

                    curr = nxt

                    while came_from[curr] is not None:

                        curr = came_from[curr]

                        path.append(curr)

                    return path[::-1]

                queue.append(nxt)

    return None

# --- Affichage lisible ---

if __name__ == "__main__":

    chemin = vider_bidon(54, 78, 37)

    print(f"Solution trouvée en {len(chemin) - 1} étapes :\n")

    for i, etape in enumerate(chemin):

        a, b, c = etape

        print(f"Étape {i:2d} : ({a:3d}, {b:3d}, {c:3d})")

Triplet initial : (54, 78, 37)

Ancien affichage (avec tri) :

Étape 0 : (37, 54, 78)
Étape 1 : (17, 74, 78)
Étape 2 : (34, 57, 78)
Étape 3 : (44, 57, 68)
Étape 4 : (11, 44, 114)
Étape 5 : (22, 44, 103)
Étape 6 : (44, 44, 81)
Étape 7 : (0, 81, 88)

Nouvel affichage (sans tri) :

Étape 0 : ( 54, 78, 37)
Étape 1 : (108, 24, 37)
Étape 2 : ( 71, 24, 74)
Étape 3 : (142, 24, 3)
Étape 4 : (139, 24, 6)
Étape 5 : (133, 24, 12)
Étape 6 : (121, 24, 24)
Étape 7 : (121, 48, 0)

EDIT:

Étape 0 : ( 54, 78, 37)
Étape 1 : (108, 24, 37) ← ( 2a, b-a, c )
Étape 2 : ( 71, 24, 74) ← ( a-c, b, 2c )
Étape 3 : (142, 24, 3) ← ( 2a, b, c-a )
Étape 4 : (139, 24, 6) ← ( a-c, b, 2c )
Étape 5 : (133, 24, 12) ← ( a-c, b, 2c )
Étape 6 : (121, 24, 24) ← ( a-c, b, 2c )
Étape 7 : (121, 48, 0) ← ( a, 2b, c-b )

Avec ma simplification :

Étape 0 : ( 54, 78, 999)
Étape 1 : (108, 24, 999) ← ( 2a, b-a, c )
Étape 2 : (216, 24, 891) ← ( 2a, b, c-a )
Étape 3 : (192, 48, 891) ← ( a-b, 2b, c )
Étape 4 : (192, 96, 843) ← ( a, 2b, c-b )
Étape 5 : (192, 192, 747) ← ( a, 2b, c-b )
Étape 6 : (384, 0, 747) ← ( 2a, b-a, c )

La simplification requiert moins d'étapes, et $c$ n'augmente jamais.

Dernière modification par syrac (24-06-2026 13:38:07)

Ernst · 24-06-2026 17:53:43

yoshi a écrit :

B'soir;
Vous disposez de 3 bidons, chacun contenant un nombre entier de litres d'eau.
On peut diminuer le contenu d'un bidon en doublant le contenu d'un autre moins rempli :
si $n_1 ≤n_2$ on passe à $2\times n_1$, avec $n_2$ ne contenant plus alors que $n_2-n_1$...
On admettra que chaque bidon est assez grand pour contenir toute l'eau mise en jeu.
Trouver un algorithme pour vider l'un des bidons au bout d'un nombre fini d'opérations.
@+

Bonjour,

La Descente Infinie, méthode binaire : l'algorithme garantit la victoire en forçant le plus petit bidon à diminuer à chaque "grand cycle", jusqu'à atteindre obligatoirement zéro.

À chaque grand cycle, on trie les 3 bidons par ordre de volume : A <= B <= C (A est le Petit, B le Moyen, C le Grand) et on effectue la division euclidienne du Moyen par le Petit :
B = q * A + r (où q est le quotient, et r le reste, donc r < A).

L'objectif du cycle est de vider exactement (q * A) litres du bidon B. Ainsi, il ne restera dans B que le reste "r". Pour y parvenir sans vider B trop tôt, on utilise le grand bidon C comme réservoir tampon. On convertit le quotient "q" en binaire et on lit le nombre binaire de DROITE à GAUCHE (du plus petit bit au plus grand) :
- si le bit est 1, on double le volume de A en piochant dans B
- si le bit est 0, on double le volume de A en piochant dans C

Puisque le reste "r" est strictement inférieur à A, la valeur minimale parmi les trois bidons diminue à chaque cycle. Dans les nombres entiers, une diminution stricte finit obligatoirement par atteindre 0.

Voici un programme Python qui illustre la chose :

def resoudre_bidons_euclide(v1, v2, v3):

    current = [v1, v2, v3]

    print(f"État Initial : {current}\n")

    cycle, step = 1, 1

    while True:

        # On trie les indices (0, 1, 2) selon la valeur actuelle des bidons (A <= B <= C)

        idx_a, idx_b, idx_c = sorted([0, 1, 2], key=lambda i: current[i])

        a, b, c = current[idx_a], current[idx_b], current[idx_c]

        if a == 0:

            print(f"✓ Terminé ! Le bidon B{idx_a + 1} est vide.")

            break

        print(f"=== GRAND CYCLE {cycle} ===")

        print(f"Tri : Petit(A)=B{idx_a+1} ({a}L) | Moyen(B)=B{idx_b+1} ({b}L) | Grand(C)=B{idx_c+1} ({c}L)")

        q, r = divmod(b, a)

        bin_q = bin(q)[2:]  # bin(5) donne '0b101', on retire le '0b'

        print(f"  Division : {b} = {q} × {a} + {r} (Reste attendu = {r}L)")

        print(f"  Quotient {q} en binaire : '{bin_q}' (lecture de droite à gauche)\n")

        # On parcourt le code binaire de droite à gauche

        for bit in reversed(bin_q):

            double_val = current[idx_a]

            source_idx = idx_b if bit == '1' else idx_c

            source_name = f"B{idx_b+1} (Moyen)" if bit == '1' else f"B{idx_c+1} (Grand)"

            # Opération de versement (on double le petit en piochant dans la source)

            current[idx_a] += double_val

            current[source_idx] -= double_val

            print(f"  • Étape {step} (Bit='{bit}') : On double B{idx_a+1} en prenant {double_val}L dans {source_name}")

            print(f"    -> [B1:{current[0]}L, B2:{current[1]}L, B3:{current[2]}L]")

            step += 1

        print(f"\n-> Fin du cycle {cycle}. Le reste obtenu est bien {current[idx_b]}L.\n")

        cycle += 1

# Lancement du test demandé

resoudre_bidons_euclide(8, 10, 11)

et voici une sortie :

État Initial : [8, 10, 11]

=== GRAND CYCLE 1 ===

Tri : Petit(A)=B1 (8L) | Moyen(B)=B2 (10L) | Grand(C)=B3 (11L)

  Division : 10 = 1 × 8 + 2 (Reste attendu = 2L)

  Quotient 1 en binaire : '1' (lecture de droite à gauche)

  • Étape 1 (Bit='1') : On double B1 en prenant 8L dans B2 (Moyen)

    -> [B1:16L, B2:2L, B3:11L]

-> Fin du cycle 1. Le reste obtenu est bien 2L.

=== GRAND CYCLE 2 ===

Tri : Petit(A)=B2 (2L) | Moyen(B)=B3 (11L) | Grand(C)=B1 (16L)

  Division : 11 = 5 × 2 + 1 (Reste attendu = 1L)

  Quotient 5 en binaire : '101' (lecture de droite à gauche)

  • Étape 2 (Bit='1') : On double B2 en prenant 2L dans B3 (Moyen)

    -> [B1:16L, B2:4L, B3:9L]

  • Étape 3 (Bit='0') : On double B2 en prenant 4L dans B1 (Grand)

    -> [B1:12L, B2:8L, B3:9L]

  • Étape 4 (Bit='1') : On double B2 en prenant 8L dans B3 (Moyen)

    -> [B1:12L, B2:16L, B3:1L]

-> Fin du cycle 2. Le reste obtenu est bien 1L.

=== GRAND CYCLE 3 ===

Tri : Petit(A)=B3 (1L) | Moyen(B)=B1 (12L) | Grand(C)=B2 (16L)

  Division : 12 = 12 × 1 + 0 (Reste attendu = 0L)

  Quotient 12 en binaire : '1100' (lecture de droite à gauche)

  • Étape 5 (Bit='0') : On double B3 en prenant 1L dans B2 (Grand)

    -> [B1:12L, B2:15L, B3:2L]

  • Étape 6 (Bit='0') : On double B3 en prenant 2L dans B2 (Grand)

    -> [B1:12L, B2:13L, B3:4L]

  • Étape 7 (Bit='1') : On double B3 en prenant 4L dans B1 (Moyen)

    -> [B1:8L, B2:13L, B3:8L]

  • Étape 8 (Bit='1') : On double B3 en prenant 8L dans B1 (Moyen)

    -> [B1:0L, B2:13L, B3:16L]

-> Fin du cycle 3. Le reste obtenu est bien 0L.

✓ Terminé ! Le bidon B1 est vide.

syrac · 25-06-2026 00:34:33

Pas mal, mais beaucoup trop compliqué (je suis persuadé qu'on peut trouver une solution simple) et fait en 8 étapes ce que Qwen fait en 4. Quelle IA as-tu utilisée ? Quel était le prompt ?

Étape 0 : ( 8, 10, 11)
Étape 1 : ( 16, 10, 3)
Étape 2 : ( 6, 20, 3)
Étape 3 : ( 6, 17, 6)
Étape 4 : ( 12, 17, 0)

Ernst · 25-06-2026 07:16:36

Bonjour,

Pour ceux qui veulent un truc rapide, voilà un programme Python qui trouve la solution la plus courte, terminé.

def solve(a,b,c):

 s=sorted([a,b,c]);q=[[s,[]]];v={tuple(s)}

 while q:

  n=[]

  for t,ops in q:

   if 0 in t:return ops+[t]

   for x,y in[(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]:

    if t[x]>=t[y]and t[y]:

     nt=list(t);nt[x]-=t[y];nt[y]*=2;nt.sort()

     k=tuple(nt)

     if k not in v:v.add(k);n.append([nt,ops+[t]])

  q=n

r=solve(8,10,11)

if r:

 for i,e in enumerate(r):print(f"{i}: {e}")

 print("VIDE")

else:print("IMPOSSIBLE")

L'idée était, me semble-t-il, de trouver un procédé qui garantissait un nombre de transferts fini, pas de faire un programme d'exploration.

Quant aux IA, j'en utilise indifféremment plusieurs et ce n’est jamais un prompt mais toujours des échanges, des questions, des demandes, donc je serais bien en peine de te répondre.

Michel Coste · 25-06-2026 08:24:48

Enfin une démonstration qui me convainc. Avoir une démonstration de la réalisabilité en temps fini à partir de toute configuration me paraît bien plus intéressant que d'avoir un programme qui explore tous les chemins possibles !
Bravo à l'I.A. qui a retrouvé cette démonstration.

yoshi · 25-06-2026 11:30:06

Bonjour,

J'ai vérifié, le programme Python fonctionne, OK ! Ça m'a surpris : j'ai eu tort de douter !
Ceci dit, quelques remarques sur la forme :
* Bourrage des lignes : ce n'est pas dans l'esprit pythonesque... Intérêt à part gagner en nombre de lignes ?
J'ai aussi programmé comme ça, il y a près de 50 ans à mes débuts, en BASIC, celui livré avec mon Amstrad CPC
6128 (il marche encore et mes disquettes aussi...)
C'est pour ça que lorsque je veux traduire différents scripts en Python, je m'arrache les cheveux.
* Indentation des blocs : la clé de voûte de tout programme Python. Recommandation de l'équipe auteur du logiciel :
4 espaces...
* Indentation utilisée par l'IA : 1 espace !!!
Croyez-moi, sur un écran 24 pouces configuré en résolution 1920 x 1200 pixels, c'est très peu lisible...

Les rectifications sont en cours, quand j'aurais fini, je chercherai à comprendre le pourquoi des contorsions : utilisation de variables chaînes, de listes, de listes de listes, d'ensembles, de n-uplets...
Je publierai le programme rectifié : chacun pourra comparer...

@+

Dernière modification par yoshi (25-06-2026 11:33:35)

Forum de mathématiques - Bibm@th.net

#1 20-06-2026 18:22:20