Problème de jarres : Mise en équations

Bonjour, je bloque sur le problème suivant :

" 2 personnes désirent se partager de manière équitable une jarre de 8 litres.Elles disposent pour cela de deux récipients vides, respectivement de 3 et 5 litres.

- Comment procéder ?
- En combien d'opérations ? "


J'ai trouvé à tâtons, une réponse en 7 opérations, le problème est que je n'arrive pas :

- A le montrer rigoureusement
- A montrer que c'est la plus petite solution possible.

J'essaie de voir quelles notions mathématiques je peux utiliser : Suites, matrices, algorithmie ...

Mais je ne vois pas de méthodes rigoureuses.

Avez-vous une idée ?

Merci

Réponses

  • Oui, 7 est bien le plus petit nombre d'opérations possible. Voici la solution optimale :
    24698
  • Merci pour la confirmation.

    Mais comment montrer que c'est la solution optimale ?
    Le graphique ci-dessus ne prouve rien .

    Cordialement
  • Regarde quels sommets tu peux atteindre en au plus 1 (resp. 2, 3, 4, 5, 6) étapes.
  • Le problème des jarres dans un livre de psychologie cognitive :

    Comme les psychologues sont vraiment très forts, ils arrivent en plus à faire neuf litres à partir de huit.

    Bon, notre ami jeremyjeff s'est noyé dans la jarre. Mais, pour voir si tout le monde a bien suivi (JLT, chut!) : toujours une jarre de huit litres à partager équitablement, mais cette fois-ci avec des récipients vides de cinq et sept litres. Combien d'opérations au minimum ?24699
  • Bonjour,

    Souvenir... avec trois jarres: Coxeter 9.

    Amicalement.
  • Hum,

    J'ai avalé la tasse, mais je reste bon nageur (:P)

    Tout cela me paraît bien empirique ...
    Il n'y a vraiment pas de méthodes plus rigoureuse, du genre matricielle , ou algorithmique (suites).
    Avec tous les outils offerts par les mathématiques, vous n'allez pas me faire croire que la seule solution est de faire un dessin (ou de compter sur ses doigts).
    je cherche encore une solution plus élégante ...


    Cordialement
  • Curieuse conception des mathématiques :D.

    Voici la preuve rigoureuse du fait que 7 est optimal.

    Plus élégant, tu meurs.24703
  • La méthode est tout à fait rigoureuse (en tout cas, on peut si on le souhaite modéliser le problème et donner une preuve suivant les lignes précédentes).

    On peut facilement obtenir un algorithme (en étudiant l'arbre des possibilités ou en se ramenant à la recherche d'un chemin optimal dans un certain graphe fini comme le suggère la présentation de Ga?).

    Ce que l'on peut éventuellement déplorer si tu veux c'est, par exemple :
    - l'absence de belles formules, d'asymptotiques, de bornes sur nombre sur le nombre de pas, ...
    - l'absence d'étude de complexité d'algorithme, de bornes sur ces complexités, d'algorithmes optimaux ou presque optimaux, ...
    - l'absence de caractérisation de la faisabilité.

    Un résultat grossier par exemple : si les contenances sont les entiers $a>b>c>0$ alors, si on peut atteindre un état, c'est en au plus $(b+1)(c+1)$ étapes (enfin, ça m'a l'air assez plausible en regardant le graphe de Ga? mais je n'ai pas vraiment réfléchi).
  • Il ne faut pas confondre "rigoureux" et "formel". Je dis ça au cas où.
  • J'attends la réponse à mon exercice avec des récipients de 5 et 7 litres...
    Ca tarde un peu.
  • Bonjour,

    Je trouve qu'il n'y a pas de solutions.

    Pour le formalisme du problème, ne peut-on pas se ramener à trouver des entiers , m,n et p tels que :
    m + n + p = 8 Litres avec des conditions de proportionnalité : multiple de 3, multiple de 5 ... ?
  • Ta question n'est pas claire. Tu dis "ne peut-on se ramener". Quel problème veux-tu ramener à quel problème ?
  • As-tu une démonstration rigoureuse du fait qu'il n'y a pas de solution ?

    La formalisation du problème qui est derrière les petits crobards :
    Si on a 3 jarres de contenance respectivement $a, b, c$ litres, et un volume total de liquide de $d$ litres.
    - On repère chaque état par un point entier $(x,y)$ du polygone décrit par $0\leq x\leq a$, $0\leq y\leq b$, $0\leq d-x-y\leq c$.
    - A chaque opération on se déplace horizontalement ou verticalement ou suivant une droite de pente $-1$, en arrêtant le déplacement exactement quand on croise un côté du polygone (NB : quand on se déplace sur un côté, on ne le croise pas). Toute extrémité de déplacement est donc sur le bord du polygone (ce qui permet de voir que l'estimation de H sur le nombre maximal d'étapes peut être largement réduite).
  • @Ga?

    Si $a=4, b=3, c=2$ et $d=3$ alors on peut avoir la suite de configuration suivante : $(3,0,0), (1,0,2), (1,2,0),(0,2,1)$. Ce dernier point est à l'intérieur du rectangle. Non ?

    Pour ton résultat, il faut donc peut-être des hypothèses sur $a,b,c,d$. Dans l'exemple initiale ça marchait mais on avait $d=a=b+c$. Je n'ai pas réfléchi davantage mais on doit pouvoir facilement tirer ça au clair.

    A moins que ce que tu dises soit que l'on peut atteindre n'importe quel point du bord en restant sur le bord. Enfin bref il manque des choses il me semble :)
  • H, tu ne m'as pas bien lu. Relis en particulier la description du polygone.
  • Effectivement, j'avais lu trop vite, désolé !
  • Je ne peux pas résister au plaisir de faire une procédure Maple :
    jarres:=proc(l)
    local k:
    n:=nops(l):lp:=combinat[permute](n,2);
    L:=[[l[1],0$(n-1)]]:T:=[0]:R:=L;
    while nops(R)>0 do
      X:=R[1];member(X,L,'k'):t:=T[k]+1:
      for p in lp do
        x:=p[1]:y:=p[2]:Y:=X;
        Y[x]:=max(0,X[x]+X[y]-l[y]);Y[y]:=min(l[y],X[x]+X[y]);
        if not member(Y,L) then print(Y,t):L:=[op(L),Y]:R:=[op(R),Y]:T:=[op(T),t] fi;
      od;
      R:=[op(2..nops(R),R)]:
    od;
    end;
    

    24708
  • Bien, voici une preuve simple et rigoureuse de l'impossibilité de réaliser le partage équitable des 8 litres avec des jarres de contenances respectives 8, 7 et 5 litres (la jarre de 8 litres étant pleine au départ :

    Chacune des trois configurations cibles (4,0), (0,4) et (4,4) (codées par le contenu des jarres de 7 et 5 litres) ne peut être atteinte qu'à partir des deux autres.

    On peut vérifier sans peine que toutes les autres configurations du bord du polygone peuvent être atteintes à partir de la configuration de départ.24763
  • Bonjour,

    Une lecture graphique ?
    C'est là la preuve ? Drôle de preuve .:S
    Je m'attendais à quelque chose de plus transcendant , comme la solution d'une équation, la convergence d'une suite .
    Je reste sur ma faim ...

    Cordialement
  • Peut-être n'as tu pas compris la preuve (assez implicite). Si à un instant tu es en $(0,4)$ par exemple, où pouvais-tu à l'état précédent ?
  • @jeremyjeff : ne te fais pas plus bête que tu n'es ! Je sais bien que tu as compris cette preuve, et compris aussi son caractère irréfutable. Pour le même prix :
    Théorème : soient $a,b,c$ des entiers avec $b>a$ et $c>a$. On suppose qu'on a une jarre de $2a$ litres pleine, et deux autres jarres vides de $b$ et $c$ litres respectivement. Il est impossible de partager équitablement les $2a$ litres en deux.
  • @Ga : je ne sais pas si jeremyjeff est vraiment de mauvaise foi. Personnellement, je n'ai pas non plus compris ta preuve...
    Il y a un dessin et tu affirmes qu'une configuration ne peut être obtenue qu'à partir de deux autres... Comment justifies-tu ceci ? Comment montres-tu par exemple qu'on n'atteint jamais les configurations (1,3), (3,1), (2,2) ?
  • @omega : Comme j'ai l'habitude de tes autres interventions, je suppose que, si tu ne comprends pas, c'est parce que tu n'as pas lu la règle du jeu expliquée dans ce message.
  • @Ga : en effet le message que mentionnes m'avait échappé. J'ai compris maintenant, merci ! [size=x-small]Peut-être que jeremyjeff est un peu de mauvaise foi, finalement... (:D [/size]
Connectez-vous ou Inscrivez-vous pour répondre.