Forum de mathématiques - Bibm@th.net

syrac

Membre

Inscription : 27-05-2014

Messages : 244

Les trois bidons revisités

Bonjour,

Ce qui suit est une simplification du problème des 3 bidons posé par Yoshi dans ce sujet, et dont je rappelle l'énoncé :

Vous disposez de trois bidons contenant chacun une quantité entière d'eau. À chaque étape vous pouvez choisir deux bidons dont les contenus sont $n_1$ et $n_2$ avec $n_1 \le n_2$. Vous versez $n_1$ litres du bidon le plus rempli vers le moins rempli. Ainsi, le contenu du bidon le moins rempli double, passant de $n_1$ à $2n_1$ litres, tandis que celui du bidon  le plus rempli diminue d'autant, passant de $n_2$ à $n_2 - n_1$ litres. Le troisième bidon n'est pas modifié. On suppose que les bidons sont suffisamment grands pour contenir toute l'eau après chaque opération.

Trouver un algorithme permettant de vider l'un des bidons ($n_x=0$) au bout d'un nombre fini d'opérations.

Ce que je nomme simplification consistait au départ en une interprétation géométrique du problème :

Considérons le segment $[0,b]$. Choisissons un point $a$ de ce segment vérifiant $0 > a \le b/2$.
On effectue l'opération suivante : le point $a$ est déplacé vers $b$ d'une distance égale à sa distance à l'origine. Il passe ainsi de la position $a$ à la position $2a$.
Le point $b$ demeure fixe.

Concrètement, j'ai créé une petite appli (adresse plus bas) qui exploite cette vision des choses. Quelques explications :

• Les triplets ne sont pas triés, les bidons ayant une position fixe.

• Ces derniers sont numérotés 1, 2, 3 de gauche à droite, numéro utilisé par l'historique (ou progression).

• L'historique reflète ce qu'on a fait pour parvenir à tel ou tel résultat. Exemple :
  0. (3, 8, 10)   [2 ← 3]
  1. (3, 16, 2)
  Signification : le triplet (3, 16, 2) a été obtenu à partir de (3, 8, 10) en doublant le bidon 2 et en désignant le bidon 3 comme "donneur" (celui qui fournit la quantité d'eau nécessaire). Sous Windows, on obtient la flèche-gauche en tapant Alt+27.

• Lorsqu'un résultat a déjà été obtenu (on tourne en rond) il est en rouge.

• Le bouton "Annuler" annule le dernier résultat, ce qui permet de corriger le tir ou d'explorer une autre piste.

EDIT : 30/06/2026. Nouvelles fonctionnalités :

Pour rendre ce qui suit plus clair je vais nommer Receveur le bidon dont on double le volume, et Donneur celui utilisé pour fournir ce complément d'eau.

L'application dispose maintenant d'un "assistant" qui intervient à deux moments :

• avant le choix du receveur l'un des bidons se voit attribuer un fond vert : il désigne celui que l'assistant considère comme le meilleur choix.

• lorsque le receveur a été sélectionné, le bouton "Donneur" devient disponible. Cliquer dessus accentue brièvement d'un fond mauve le bidon que l'assistant considère comme le meilleur donneur.

Bien entendu, rien n'oblige à suivre ces recommandations ; elles n'ont d'autre utilité que d'éviter le blocage face à un choix difficile.

NB :

• La progression des étapes recommandées par l'assistant n'est pas nécessairement la même que celle fournie par un script Python ou autre, mais elle s'effectue dans le même nombre d'étapes.

• Il peut arriver que deux bidons représentent un bon choix, aussi bien comme receveur que comme donneur. L'appli n'en suggère cependant qu'un seul, aléatoirement, ce qui fait que la progression peut changer.

Autre amélioration : sélectionnez un triplet quelque part (éventuellement entre parenthèses ou crochets), cliquez sur le champ "Volume du bidon 1", et enfin pressez Ctrl+V (copier-coller) pour renseigner les trois champs simultanément.

EDIT 2 : 01/07/2026. Nouveau : deux modes de fonctionnement sont désormais disponibles :

• En mode Assistance, l'application suggère le meilleur receveur et peut, à la demande, indiquer le meilleur donneur afin de vous guider vers une solution (un bidon vide). C'est ce que j'ai annoncé il y a peu (premier EDIT).

• En mode Exploration, toute assistance visuelle disparaît. Un panneau latéral présente les différentes possibilités offertes à chaque étape, en indiquant pour chaque couple receveur/donneur le nombre minimal d'étapes restant avant la solution. Vous pouvez ainsi choisir librement votre stratégie, suivre le chemin le plus court ou au contraire explorer des itinéraires plus longs et découvrir d'autres comportements du système.

  Dans l'exemple suivant le triplet de départ (étape 0) est (550, 179, 1152). Voici ce qu'affiche l'explorateur :
  
  Nous voyons qu'à cette étape il existe trois manières de poursuivre notre chemin vers une solution :

  1. Sélectionner le receveur 550, qui nous laisse une seule possibilité de donneur : 1152 → 9. Le chiffre après la flèche représente la distance minimale, en nombre d'étapes, jusqu'à une solution.

  2. Sélectionner le receveur 179, qui nous laissera le choix du donneur 550 grâce auquel nous pourrons aboutir à une solution en 5 étapes,

  3. ou celui du donneur 1152 dont le chemin vers une solution sera plus long (8 étapes).

  Si nous souhaitons trouver le chemin le plus court nous choisirons clairement le receveur 179 puis le donneur 550. Mais ce qui est plus amusant c'est de tester différents chemins, et à ce propos j'ai ajouté un bouton "Répéter", qui permet de repartir du même triplet. Une piste de recherche intéressante est de choisir systématiquement le couple receveur/donneur qui affiche la distance la plus longue. Je suis ainsi arrivé à 64 étapes à partir du triplet (786, 231, 471). Je précise qu'à chacune d'elles l'appli vérifie si le nouveau triplet existe déjà dans l'historique ou en est une permutation. Si c'est le cas elle l'affiche en rouge (doublon) ou orange (permutation).

  Ce qu'on observe est que la progression devient de plus en plus difficile à cause des doublons et/ou permutations qui obligent à revenir en arrière (bouton Annuler) pour faire un autre choix. Mais une question se pose : existe-t-il des chemins vraiment très longs ?

L'application en question se trouve à cette adresse.

Dernière modification par syrac (02-07-2026 14:31:08)

syrac

Membre

Inscription : 27-05-2014

Messages : 244

Re : Les trois bidons revisités

Premier résultat encourageant : aussi bien l'algo de Yoshi que celui de Ernst donnent ce résultat (au format de mon appli)

0. (3, 8, 13) [1 ← 2]
1. (6, 5, 13) [1 ← 3]
2. (12, 5, 7) [2 ← 1]
3. (7, 10, 7) [1 ← 3]
4. (14, 10, 0)

Mon appli a permis de trouver un autre chemin :

0. (3, 8, 13) [1 ← 3]
1. (6, 8, 10) [1 ← 3]
2. (12, 8, 4) [3 ← 1]
3. (8, 8, 8) [1 ← 2]
4. (16, 0, 8)

Quoi qu'il en soit, il existe 13 triplets dont la somme est 24 et qui contiennent un seul zéro. Dans Mathematica, faire

DeleteDuplicates[
  Sort /@ Select[
    Tuples[Range[0, 24], 3],
    Total[#] == 24 && MemberQ[#, 0] &
  ]
]

ce qui donne

{{0, 0, 24}, {0, 1, 23}, {0, 2, 22}, {0, 3, 21}, {0, 4, 20}, {0, 5, 19}, {0, 6, 18}, {0, 7, 17}, {0, 8, 16}, {0, 9, 15}, {0, 10, 14}, {0, 11, 13}, {0, 12, 12}}

J'ai mis les deux déjà trouvés en gras. Il en reste 11, mais reste à savoir si le triplet (3, 8, 13) de départ permet ou non de les produire.

Dernière modification par syrac (28-06-2026 17:26:58)

Ernst

Membre

Inscription : 30-01-2024

Messages : 369

Re : Les trois bidons revisités

Hello syrac,

Si cela peut t'aider, ici > une page < qui trouve toutes les solutions les plus courtes avec indications des transferts.

syrac

Membre

Inscription : 27-05-2014

Messages : 244

Re : Les trois bidons revisités

Hi Ernst,

Merci, bien que le triplet dont j'ai parlé ne soit pas (3, 5, 8) mais (3, 8, 13). Peux-tu refaire tes calculs et surtout expliquer la démarche plutôt que les résultats bruts ?

EDIT : ne te casse pas la tête, ton exemple est trop simple, surtout que mon appli donne la solution sans avoir besoin de cliquer (tu places simplement ta souris sur le 3 ou sur le 5). Ce qui serait formidable c'est que tu partes de (3, 8, 13) pour aboutir à un triplet contenant un zéro mais inconnu jusqu'à présent, quel que soit le nombre d'étapes (parce que je soupçonne qu'il en faudra plus pour atteindre certains zéros).

Dernière modification par syrac (29-06-2026 10:07:38)

Ernst

Membre

Inscription : 30-01-2024

Messages : 369

Re : Les trois bidons revisités

Hello syrac,

Normalement il suffit de changer les valeurs dans les champs et cliquer sur 'Go', ça ne marche pas ?

Dernière modification par Ernst (29-06-2026 11:20:56)

syrac

Membre

Inscription : 27-05-2014

Messages : 244

Re : Les trois bidons revisités

Disons que mon appli est un explorateur interactif (ou BFS manuel guidé par la réflexion), la tienne un BFS automatisé. Mais contrairement à ce qu'on pourrait en déduire, je ne suis pas contre le fait de déléguer nos fonctions cognitives à des machines !

syrac

Membre

Inscription : 27-05-2014

Messages : 244

Re : Les trois bidons revisités

L'application réunit maintenant le meilleur des deux mondes : 1) un explorateur interactif, 2) un assistant au choix.

Je ne vais pas réitérer les explications que j'ai fournies dans mon premier message après l'avoir édité, alors merci à vous de remonter jusqu'à lui.

EDIT : je viens de modifier un comportement, illustré par cette phrase : "Il peut arriver que deux bidons représentent un bon choix, aussi bien comme receveur que comme donneur. L'appli n'en suggère cependant qu'un seul, aléatoirement, ce qui fait que la progression peut changer."

Dernière modification par syrac (30-06-2026 12:50:02)

syrac

Membre

Inscription : 27-05-2014

Messages : 244

Re : Les trois bidons revisités

Nouvelle fonctionnalité : voir EDIT 2 dans mon premier message.

syrac

Membre

Inscription : 27-05-2014

Messages : 244

Re : Les trois bidons revisités

Je viens de terminer une progression de 777 étapes sans doublon et sans permutation ... et sans zéro. Pour la charger dans l'appli, sélectionnez-la (Ctrl+A) puis copiez-la (Ctrl+C), cliquez sur le nouveau bouton "Importer" et collez-la (Ctrl+V).

Bien sûr, depuis n'importe lequel de ces 777 triplets on peut descendre rapidement vers un zéro. Ma stratégie pour rester "en altitude" en mode Exploration :

1. Si toutes les distances sont égales je sélectionne le plus petit receveur et le plus grand donneur, de manière à équilibrer les volumes puisque le receveur double et que le donneur diminue d'autant.

2. Sinon je sélectionne le couple receveur/donneur qui correspond à la plus grande distance.

Il est probable qu'en revenant suffisamment en arrière j'aurais trouvé un chemin qui m'aurait permis d'aller au-delà de 777 étapes, mais j'ai estimé que pour un test effectué manuellement c'était suffisant. Pour la suite j'envisage d'automatiser la procédure afin de voir si des chemins de plusieurs milliers d'étapes sans tomber sur un zéro sont possibles.

L'algorithme de parcours en largeur permettrait également de tracer le graphe du chemin à partir d'un triplet donné jusqu'au plus proche zéro (ou plus proches zéros).

Tout ceci est toujours sur le Problème des trois bidons