Forum de mathématiques - Bibm@th.net

Ernst

Membre

Inscription : 30-01-2024

Messages : 359

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 : 237

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 (Aujourd'hui 15:56:41)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 496

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 (Aujourd'hui 16:11:32)

syrac

Membre

Inscription : 27-05-2014

Messages : 237

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 : 237

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 (Aujourd'hui 18:32:03)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 496

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 (Aujourd'hui 17:38:14)

syrac

Membre

Inscription : 27-05-2014

Messages : 237

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 421

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,

@+
@+