Forum de mathématiques - Bibm@th.net

Ernst

Membre

Inscription : 30-01-2024

Messages : 370

Re : Encore une histoire de bidons

Bonjour yoshi,

Voici, spécialement pour toi, un programme que tu devrais pouvoir mieux suivre :

"""
Problème des trois bidons - Résolution par BFS avec traçage complet.

Principe : on a trois bidons de contenance illimitée (en pratique assez grande).
Une opération consiste à prendre deux bidons A et B tels que A contient au moins
autant que B (et B non vide), puis à vider B dans A :
    A <- A - B
    B <- B * 2
Le but est d'arriver à un état où l'un des trois bidons est vide.
"""

def trier_etat(liste):
    """
    Retourne une copie triée par ordre croissant d'une liste de trois entiers.
    Cette fonction remplace sorted() pour éviter d'importer quoi que ce soit,
    même si sorted() est built-in. On fait simple : insertion manuelle.
    """
    a, b, c = liste[0], liste[1], liste[2]
    # Tri par insertion pour trois éléments (oui, c'est du luxe pédagogique)
    if a > b:
        a, b = b, a
    if b > c:
        b, c = c, b
    if a > b:
        a, b = b, a
    return [a, b, c]

def trouver_solution(bidon1, bidon2, bidon3):
    """
    Recherche une séquence d'opérations pour vider un bidon.

    Args:
        bidon1, bidon2, bidon3 (int): contenus initiaux des trois bidons

    Returns:
        list ou None : liste des étapes avec descriptions détaillées,
                       ou None si impossible.
    """
    # État initial trié (ordre canonique : petit, moyen, grand)
    # On garde aussi la liste non triée pour l'affichage initial.
    depart = [bidon1, bidon2, bidon3]
    etat_initial = tuple(trier_etat(depart))

    # La file pour le BFS : chaque élément est un dictionnaire contenant :
    #   - 'etat'   : le tuple trié de l'état courant
    #   - 'chemin' : la liste des descriptions d'étapes déjà faites
    file = []
    # Description de l'état initial
    desc_initiale = (
        f"État initial : ({depart[0]}, {depart[1]}, {depart[2]}) "
        f"-> trié : ({etat_initial[0]}, {etat_initial[1]}, {etat_initial[2]})"
    )
    file.append({
        'etat': etat_initial,
        'chemin': [desc_initiale]
    })

    # Ensemble des états visités (tuples triés) pour éviter les cycles
    visites = set()
    visites.add(etat_initial)

    # Les 6 paires (source, cible) possibles
    paires = [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]

    while len(file) > 0:
        # Dépiler le premier élément (FIFO = BFS)
        courant = file.pop(0)
        etat = courant['etat']
        chemin = courant['chemin']

        # Critère d'arrêt : un bidon vide
        if 0 in etat:
            return chemin

        # Tenter tous les transferts
        for source, cible in paires:
            qte_source = etat[source]
            qte_cible = etat[cible]

            # Condition du transfert :
            # - source doit avoir au moins autant que cible
            # - cible ne doit pas être vide (sinon 0*2 = 0, aucun changement)
            if qte_source >= qte_cible and qte_cible > 0:
                # Nouvel état avant tri
                nouveau = list(etat)
                nouveau[source] = qte_source - qte_cible
                nouveau[cible] = qte_cible * 2

                # On le trie pour la forme canonique
                etat_trie = tuple(trier_etat(nouveau))

                # Si pas encore visité
                if etat_trie not in visites:
                    visites.add(etat_trie)

                    # --- Construction de la description détaillée ---
                    # Pour rendre l'explication claire, on affiche les indices
                    # dans l'état trié, et on reconstitue ce que ça donne.
                    avant = etat
                    apres = list(etat_trie)

                    # On indique le transfert avec les quantités réelles
                    desc = (
                        f"Étape {len(chemin)} : "
                        f"bidon {source} (contenait {qte_source}) "
                        f"verse dans bidon {cible} (contenait {qte_cible}) "
                        f"-> avant tri : {nouveau} "
                        f"-> après tri : ({apres[0]}, {apres[1]}, {apres[2]})"
                    )

                    nouveau_chemin = chemin + [desc]
                    file.append({
                        'etat': etat_trie,
                        'chemin': nouveau_chemin
                    })

    # Aucune solution
    return None

def afficher_solution(chemin):
    """
    Affiche le chemin complet vers la solution.
    """
    if chemin is None:
        print("Aucune solution trouvée.")
        return

    print("=" * 70)
    print("SOLUTION TROUVÉE")
    print("=" * 70)
    for ligne in chemin:
        print(ligne)
    print("=" * 70)

    # Extraire le nombre d'opérations (la première ligne est l'état initial)
    nombre_operations = len(chemin) - 1
    print(f"Nombre d'opérations : {nombre_operations}")
    derniere_ligne = chemin[-1]
    print(f"Dernier état : {derniere_ligne}")
    print("Un bidon est vide : objectif atteint !")
    print("=" * 70)

# ==============================================================================
# Programme principal
# ==============================================================================
if __name__ == "__main__":
    print("Recherche de solution pour les bidons de 8, 10 et 11 litres...\n")
    solution = trouver_solution(8, 10, 11)
    afficher_solution(solution)

    # Exemple supplémentaire (décommenter pour tester)
    # print("\n\nRecherche pour les bidons de 3, 5 et 8 litres...\n")
    # solution2 = trouver_solution(3, 5, 8)
    # afficher_solution(solution2)

Sortie :

Recherche de solution pour les bidons de 8, 10 et 11 litres...

======================================================================
SOLUTION TROUVÉE
======================================================================
État initial : (8, 10, 11) -> trié : (8, 10, 11)
Étape 1 : bidon 2 (contenait 11) verse dans bidon 0 (contenait 8) -> avant tri : [16, 10, 3] -> après tri : (3, 10, 16)
Étape 2 : bidon 2 (contenait 16) verse dans bidon 1 (contenait 10) -> avant tri : [3, 20, 6] -> après tri : (3, 6, 20)
Étape 3 : bidon 2 (contenait 20) verse dans bidon 0 (contenait 3) -> avant tri : [6, 6, 17] -> après tri : (6, 6, 17)
Étape 4 : bidon 0 (contenait 6) verse dans bidon 1 (contenait 6) -> avant tri : [0, 12, 17] -> après tri : (0, 12, 17)
======================================================================
Nombre d'opérations : 4
Dernier état : Étape 4 : bidon 0 (contenait 6) verse dans bidon 1 (contenait 6) -> avant tri : [0, 12, 17] -> après tri : (0, 12, 17)
Un bidon est vide : objectif atteint !
======================================================================

Pour pouvoir le lire sur un petit écran haute résolution, il suffit de faire [Ctrl][+] et [Ctrl][-] dans n’importe quel navigateur, c’est le principe même de la lisibilité tous supports.

syrac

Membre

Inscription : 27-05-2014

Messages : 246

Re : Encore une histoire de bidons

@Ernst, je dois dire que je suis impressionné par la fonction 'solve(a,b,c)', qui t'a permis de passer d'une usine à gaz à une solution concise.

J'ai demandé à ChatGPT de lancer une recherche exhaustive sur des petites sommes $a+b+c$ en utiisant les règles définies dans l'énoncé. Il a cherché jusqu'à 500 sans tomber sur une impossibilité (un triplet de départ qui ne tombe jamais sur un autre contenant 0). Tout comme avec le problème de Collatz, ce genre de test ne constitue pas une preuve : on sait que le triplet cible existe, mais on ne sait pas si on pourra l'atteindre à partir de celui de départ. Dans les deux cas il reste à trouver une démonstration, et je trouve que de ce point de vue il existe une similitude entre les deux problèmes.

EDIT :

L'approche "à la Collatz" consisterait à noter que le triplet $(a,3a,c)$ atteint 0 en 2 étapes, et il en existe une infinité. Ensuite on se demanderait quel triplet a pour successeur $(a,3a,c)$, puis ... Et là on deviendrait fou, comme avec Collatz. ❌⛔

Dernière modification par syrac (25-06-2026 15:56:41)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 520

Re : Encore une histoire de bidons

La démonstration a été donnée.  Il suffit de lire et de comprendre. Je la redonne.

Elle est assez facile à comprendre. Elle repose sur le lemme suivant :
Ètant donné une configuration $(a,b,c)$ avec $0 <  a \leq b \leq c$, il existe une suite d'opérations autorisées qui amène à une configuration $(a',b',c')$ avec $b' <a$.
Cette suite d'opérations se construit ainsi. On fait la division euclidienne de $b$ par $a$ : $b = aq +b'$ avec $0\leq b'<a$, et on écrit le quotient $q$ en binaire : $q = \sum_{i=0} ^n \epsilon_i 2^i$ où les bits $\epsilon_i$ sont égaux à 0 ou à 1, et $\epsilon_n=1$. On fait la suite d'opérations à partir de $(a_0,b_0,c_0)=(a,b,c)$ donnée pour $k=1,\ldots,n$ par

• $a_k=2a_{k-1}= 2^k a$ ,

• $b_k=b_{k-1}-\epsilon_k a_{k-1}=b-\left(\sum_{i=0}^k\epsilon_i 2^i\right)a$ ,

• $c_k=c_{k-1}-(1-\epsilon_k )a_{k-1}=c-\left(\sum_{i=0}^k(1-\epsilon_i )2^i\right)a$ .

Remarquons que toutes ces opérations sont bien valides car on a  $b_k\geq 0$ et $c_k>0$ pour tout $k $ de $1$ à $n$. Au bout de ces $n$ opérations on obtient $(a_n,b_n,c_n)$ où $b_n=b-qa=b' < a$.

Par le lemme on sait faire baisser strictement, par un nombre fini d'opérations autorisées,  le minimum des contenus des trois bidons pour n'importe quelle configuration où ce minimum est non nul. On finira donc au bout d'un nombre fini d'opérations autorisées par amener ce minimum à $0$.

Dernière modification par Michel Coste (25-06-2026 16:11:32)

syrac

Membre

Inscription : 27-05-2014

Messages : 246

Re : Encore une histoire de bidons

@Michel Coste,

Etant plus porté vers le développement web que vers les maths, j'ai dû demander à ChatGPT de m'expliquer cette démonstration, laquelle me réjouit grandement : personne ne deviendra fou à cause de ce problème ! ☑

syrac

Membre

Inscription : 27-05-2014

Messages : 246

Re : Encore une histoire de bidons

[suite]

D'ailleurs c'est un excellent test sur les capacités de ChatGPT en maths. Comme je lui avais passé une capture de ta démo (sinon il m'aurait fallu une heure pour la convertir en LaTeX), il m'a répondu sous la même forme (?). Une critique envers ses explications ?

EDIT :

Croyez-moi, sur un écran 24 pouces configuré en résolution 1920 x 1200 pixels, c'est très peu lisible...

Tu n'as qu'à t'acheter un BenQ RD240Q (24 pouces, 2560x1600) avec la mise à l'échelle de 125 % recommandée par Windows 11 (et appliquée par défaut). Augmenter la densité de pixels augmente la lisibilité du texte, surtout lorsqu'il est petit, sans modifier la perception de l'échelle. On le constate quotidiennement en utilisant un smartphone.

Dernière modification par syrac (25-06-2026 18:32:03)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 520

Re : Encore une histoire de bidons

Dans les quelques modifications que ChatGPT fait à ce que j'ai écrit, il ne peut pas s'empêcher d'ajouter quelque chose de complètement idiot:

le minimum des trois bidons diminue strictement (ou au moins ne reste pas le même)

Syrac, ne peux-tu pas comprendre la démonstration par toi-même, sans passer par une I.A. ?

Dernière modification par Michel Coste (25-06-2026 17:38:14)

syrac

Membre

Inscription : 27-05-2014

Messages : 246

Re : Encore une histoire de bidons

Utiliser une IA devient un réflexe. Dès que quelque chose paraît un peu ardu, beaucoup de gens — dont j'ai tendance à faire partie — se tournent vers l'IA. C'est beaucoup plus pratique et rapide que de faire un effort pour comprendre. Je sais, c'est une solution de facilité qui à long terme peut se révéler une nuisance. Mais il faut distinguer deux choses : ce qu'on apprend et dont on est sûr que ça nous sera utile à l'avenir, et ce dont on prend connaissance à titre d'information et qu'on ne ressent pas le besoin de tranformer en savoir. Dans le cas de ta démonstration, j'ai demandé à ChatGPT de me l'expliquer parce que j'avais envie de comprendre, mais sans aller jusqu'à reprendre des études de maths.

En réalité, ce que je sais des maths c'est ce que j'ai appris moi-même au cours de ma recherche de longue haleine sur la conjecture de Collatz, ajouté à un attrait prononcé pour l'algèbre.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 496

Re : Encore une histoire de bidons

Re,

@Ernst

Pour pouvoir le lire sur un petit écran haute résolution, il suffit de faire [Ctrl][+] et [Ctrl][-] dans n’importe quel navigateur, c’est le principe même de la lisibilité tous supports.

    Ah, je ne vois que tu n'as pu t'en empêcher...
    As-tu réfléchi une seconde en te demandant comment celui qui te lit l'interpréterait ?
    Non, il fait trop chaud pour ça... C'est bien vrai
    Donc voilà :
    Cela veut dire que, étant donné que j'ai commencé à programmer il y a près de 50 ans et donc bien que j'ai eu entre les mains, un certain nombre d'écrans de toutes tailles, de toutes marques, je n'ai pas été capable de connaître cette manip si courante...
    Alors, jeune homme, tu ne sais probablement pas ou tu n'as pas Python  installé sur ta bécane, que Python est livré avec un soft nommé Idle qui permet de lire, écrire , éditer, exécuter les scripts (il existe des tas d'autres softs qu'on peut télécharger pour le remplacer et travailler avec, je sais...)...
Mais il se trouve que je suis à l'aise avec et que je ne l'ai pas remplacé malgré son petit défaut : CTRL+ ou CRTL- sont inopérants sur lui !
D'origine, cet Idle est même réglé à n'afficher que 80 caractères par ligne : ça je le modifie à chaque nouvelle version de Python e modifiant les réglages internes..
Mais si je peux augmenter le nombre de caractères par ligne, ce n'est pas pour autant que je peux augmenter leur taille...

Vois-tu, mais ça tu ne pouvais pas le  savoir, pendant des années (au moins 15) jusqu'à mon départ en retraite, j'ai assumé le rôle d'AIPRT Animateur Informatique Personne Ressource Technique... Je gérais le réseau informatique pédagogique (80 machines) et 2 serveurs, un avec windows server, l'autre avec un Linux installé configuré en serveur Internet.
Je devais entre autre, former, aider mes collègues...
Crois-moi, nombreux étaient ceux qui avaient besoin de mes services, pour des pbs insignifiants (pour moi, pas pour eux)...
La documentaliste me fait signe :
- mon imprimante ne marche plus, tu peux jeter un oeil...
- j'ai fait attention au choix des mots que j'ai utilisés : Ton imprimante fonctionne... Autant que possible,  garde un œil sur ton matériel, un élève t'a fait une blague, il a dévissé, puis débranché le câble de l'imprimante à l'arrière de ta machine (c'était un gros câble, un de ceux d'avant l'avènement de l'USB)
En salle informatique  :
- l'écran du poste n° tant ne s'allume plus, tu peux regarder ? C'était simplement le câble d'alimentation que quelqu'un avait tripoté : la fiche n'était plus assez enfoncé dans sa multiprise tout en donnant l'impression que tout était normal... Il m'avait suffit de le réenfoncer.
- Une autre fois, j'arrive en Salle info : ah bin tu tombes bien, le poste là-bas (me le désignant) ne se connecte plus à Internet : quelqu'un avait retiré la fiche RJ45 de son logement...
Ce sont des exemples gentils, je suis resté courtois.
Par contre, un de mes collègues AIPRT dans un autre Collège avait trouvé trouvé dans son casier ce petit mot (non  signé) : il n'y a plus de papier dans l'imprimante réseau (une ramette était à disposition), merci d'en remettre... Lui n'avait que peu apprécié. et l'avait fait savoir...
J'ai même eu un cas épineux : une remplaçante s'installe avec une classe en Salle Info et donne la consigne suivante : << Pour l'exposé que vous avez à faire ; vous allez chercher un sujet sur Google... >>.
Je la prends à part et je lui demande si elle avait déjà fait ça... Réponse : oui, oui, t'inquiète pas... (ce n'était pas pour me rassurer). Je sui sorti pour la laisser bosser...
Après son passage, j'étais retourné inspecter les machines : j'avais eu du boulot...
Enfin, une autre fois, une collègue avait dû cliquer à répétition sur la mention imprimer : elle voulait imprimer un texte de 4 pages...
L'imprimante ne s'était arrêtée qu'à court de feuilles : elle avait demandé en fait l'impression d'une centaine d'exemplaires de son texte...
Encore une fois, j'avais fait attention à ne pas me montrer désobligeant malgré moi...
Ca c''était le côté hard...
La partie Soft de ma tâche consistait, entre autres, à former les profs volontaire à l'utilisation de Word et/ou Excel, voire à utiliser plus tard la suite OpenOffice au lieu de celle de Microsoft...
Si je ne m'étais pas surveillé, répondu tout à trac et fait des remarques inconsidérées, je n'aurais pas tenu 15 ans...

Sans rancune,

@+
@+

Ernst

Membre

Inscription : 30-01-2024

Messages : 370

Re : Encore une histoire de bidons

    Ah, je ne vois que tu n'as pu t'en empêcher...
    As-tu réfléchi une seconde en te demandant comment celui qui te lit l'interpréterait ?
    Non, il fait trop chaud pour ça... C'est bien vrai

Bonjour yoshi,

Il se trouve que j'ai simplement essayé de répondre à ton casse-tête dans l'esprit que je supposais au forum. Le premier programme était là pour montrer le fonctionnement de l'algorithme, le second pour montrer qu'on peut également avoir une démarche exploratoire du plus court chemin. Strictement rien d'autre.

Comme mon programme n’avait pas l’air de te plaire, je t’ai proposé un programme plus détaillé et une manipulation élémentaire. Personne n'aurait pu deviner, en 2026, que tu en étais resté à des outils obsolètes, et j'en suis désolé.

Ernst

Membre

Inscription : 30-01-2024

Messages : 370

Re : Encore une histoire de bidons

Bonjour,

Je publierai le programme rectifié : chacun pourra comparer...

Chiche !

from collections import deque
def solve(a,b,c):
 q=deque([((s:=tuple(sorted((a,b,c))),[s]))]);v={s}
 while q:
  (t,p)=q.popleft()
  if 0 in t:return p
  for i,j in[(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]:
   if 0<t[i]<=t[j]:
    n=tuple(sorted((t[i]*2,t[j]-t[i],t[3-i-j])))
    if n not in v:v.add(n);q.append((n,p+[n]))
for i,e in enumerate(solve(851,1878,844)):print(f"{i}: {list(e)}")

https://ibb.co/wkVMt4d

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 496

Re : Encore une histoire de bidons

RE,

chiche !

Provoc infantile et parfaitement inutile...
T'as pas passé l'âge de jouer à celui qui a la plus longue, à celui qui pi... le plus loin ?
Tu crois que j'ai besoin de ça pour faire ce que je dis ? Tu me déçois...
J'ai promis un code sans ligne bourrée et bien indenté, je n'ai pas promis de modifier le code, seulement sa présentation (je ne suis pas inconscient !).
Donc,  voilà ce que j'appelle un code propre :

#!/usr/bin/python
# -*- coding: utf-8 -*-

from collections import deque

def solve(a,b,c):
    q=deque([((s:=tuple(sorted((a,b,c))),[s]))])
    v={s}
    while q:
        (t,p)=q.popleft()
        if 0 in t:
            return p
        for i,j in[(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]:
            if 0<t[i]<=t[j]:
                n=tuple(sorted((t[i]*2,t[j]-t[i],t[3-i-j])))
                if n not in v:
                    v.add(n)
                    q.append((n,p+[n]))

for i,e in enumerate(solve(851,1878,844)):
    print(f"{i}: {list(e)}")

N'est-ce pas plus lisible ?

@]+

Bernard-maths

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 917

Re : Encore une histoire de bidons

Celui qui pi le plus loin doit connaître un grand nombre de décimales ... (;-)    -^v^-

En 1970 en certif de analyse numérique on apprenait le Fortran, puis l'Algol ...

La structure indentée des programmes n'était pas à l'ordre du jour encore !

Mais il y avait déjà les crayons billes 4 couleurs, et j'avais structuré un programme en faisant des "indentations en couleurs".

Cela avait beaucoup plu à notre assistante ...

Bonne suite dans vos joutes orales,

B-m

Dernière modification par Bernard-maths (26-06-2026 15:23:18)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 496

Re : Encore une histoire de bidons

Re,

Toi aussi, tu as tâté de l'ALGOL ? Je dois encore avoir le manuel que j'avais acheté...
On pondait un programme qui nous revenait avec la mention sur du papier listing  : Erreur Algol en ligne xx

Remède contre la programmation : ce retour s'effectuait souvent 15 j plus tard. A ce moment-là, on était déjà passé à autre chose...
De toute l'année, on n'avait jamais vu l'ombre d'une machine baptisée ordinateur (et à travers ?)...

@+

Bernard-maths

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 917

Re : Encore une histoire de bidons

Re,

On tapait sur des claviers, impression sur papier listing, programmation sur bande perforée ... retour assez rapide le lendemain.

@

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 496

Re : Encore une histoire de bidons

B'soir,

@Bernard-maths .
Et bien, vous étiez mieux lotis que nous (c'était en 1969)...

@Ernst
Allez, j'ose...
Tant qu'à utiliser un fstring pourquoi ne pas le retoucher, histoire de rendre l'affichage un peu plus esthétique ?
Comme ça, tiens :

[ 0:  844, 851,1878]
[ 1:  844,1027,1702]
[ 2:  675, 844,2054]
[ 3:  844,1350,1379]
[ 4:  506,1379,1688]
[ 5: 1012,1182,1379]
[ 6:  197,1012,2364]
[ 7:  394, 815,2364]
[ 8:  421, 788,2364]
[ 9:  421,1576,1576]
[10:    0, 421,3152]

   
Voilà la modif, remplacement de la dernière ligne par :

    print(f"[{i:2d}: {e[0]:4d},{e[1]:4d},{e[2]:4d}]")
 

Mais je trouve le code modifié un peu "rustique"...

Zoom.
Je n'y ai pensé qu'à retardement, M'enfin, " Mieux vaut tard que jamais !" paraît-il...
Même si idle.pyw n'est pas très performant, sa version est mise à jour avec chaque dernière version de Python...
Des versions Bugfix de Python v. 3.14 sont publiées au rythme de 1 tous les 2 mois...
La 1ere version de Python 3.15 est prévue pour l'an prochain...
Je travaille encore avec la version 3.8.10  de Python et le idle.pyw qui va avec date de janvier 2023...
Il ne remonte donc pas à Mathusalem... Si ?

Bon, j'ai finalement pensé à copier ton code et le coller dans swriter, le Traitement de Textes de la dernière suite bureautique de Apache OpenOffice...
Et là, via CTRL + roulette, j'ai pu zoomer suffisamment pour obtenir des certitudes concernant l'indentation et le débourrage à faire...
Une fois terminé, j'ai copié le résultat, l'ai retransféré dans idle.pyw et testé...

@+