un peu de réflexion

[invitec4044652]

une personne doit aller chercher 4L d'eau à une source. Elle doit faire un seul trajet et n'a pour emmener l'eau que:un bocal de 3L et un bocal de 5L. Comment fait-elle??? Bonne réflexion
-----

[invitec81515bd]

Un Classique !

J'ai, mais je vous demande de me croire sur parole, sinon il n'y aurait plus de réflexion.

[matthias]

Elle remplit son bocal de 3L, le vide dans celui de 5L.
Elle remplit son bocal de 3L, verse ce qu'elle peut dans celui de 5L.
Il lui reste donc 1L dans le bocal de 3L.
Elle vide celui de 5L.
Elle vide le bocal de 3L dans celui de 5L.
Elle remplit le bocal de 3L et le vide dans celui de 5L.

[matthias]

En voici une un peu plus dure.

On dispose de trois récipients.
Au départ chaque récipient contient un nombre entier de litres d'un liquide.
Chaque récipient est suffisament grand pour contenir tout le liquide.
La seule opération autorisée est : si un récipient contient n litres, prendre un récipient qui contient au moins n litres, verser n litres dans le premier (le premier contient alors 2n litres).

Montrer que quelle que soit la configuration initiale, on peut toujours vider un des récipients.

[A voir en vidéo sur Futura]

[invitec81515bd]

J'avais une autre solution :

Elle remplit le bocal de 5l. Le vide dans celui de 3. Il lui reste 2 l dans celui de 5l.
Elle vide celui de 3l, et transvase ce qui reste de celui de 5l dans le 3l vide.
Elle re-remplit celui de 5l et verse le liquide dans celui de 3l jusqu'à le remplir.
Comme il n'y avait de la place que pour un litre dans celui de 3l, il reste 4 litres dans le bocal.

Pour la seconde, je dois avouer que c'est plus flou, mais j'y réfléchit !

[matthias]

J'avais une autre solution :

Ta solution est plus rapide (6 étapes, contre 8 pour la mienne). Est-elle optimale ?

[invitec81515bd]

Ta solution est plus rapide

J'osai pas le dire...

Aussi, je crois avoir optimisé la tienne : 7 contre 8 : à la fin après avoir rempli celui de 3l, elle ne le transvase pas et revient avec 3 litres dans un bocal et 1 litre dans l'autre. Deux mains pour un trajet, ça reste conforme à l'énoncé !

Pas contre, sur l'optimalité de ma solution, je n'en ai aucune idée. Mais je serai assez curieux de savoir si il y a une méthode pour évaluer cela (ça ne fait pas du tout partie de mon bagage) !
Merci d'avance.

[invitec4044652]

jess n'ohm, CT la solution attendu car la plus rapide. par contre Matthias, pour ton énoncer, je continu a reflechir

[mayonaise]

Ouais, le seul truc, c'est que si on a 3 récipients a, b et c contenant respectivement a, b et c litres avec a<b<c, on devrait pouvoir verser de b a litres->a et de c 2ⁿ (b-a) litres dans b, mais rien ne nous indique que dans c on ait 2ⁿ (b-a) (ou que dans b on ait 2ⁿ (c-a) ) qui me semble être une condition nécessaire au bon fonctionnement du truc muche...

[matthias]

J'avoue ne pas bien avoir compris ton raisonnment ni ta condition mayonnaise ...

[Evil.Saien]

J'ai l'impression que ce problème ressemble aux disques de Hanoï...

[matthias]

J'ai l'impression que ce problème ressemble aux disques de Hanoï...

Intéressant comme idée. Je me demande si on peut trouver une équivalence complète entre les deux problèmes. A creuser.
Tu disais ça par intuition, ou tu as vraiment une équivalence à nous soumettre ?

Sinon pour le problème initial, on peut commencer par démontrer que tant qu'aucun récipient n'est vide (et donc que le volume minimum des trois récipients est N > 0), il existe une suite de manipulations qui permettent d'obtenir un minimum n < N. On obtient ainsi une suite d'entiers strictement décroissante (et qui atteint donc 0 en un nombre fini d'étapes). On peut penser par exemple au reste par une division euclidienne ....

[heruhur]

Je me trompe peut-être mai on peut aussi remplir les 2 bocaux à moitié :
5/2=2,5
3/2=1,5
2,5+1,5=4L
Faut juste savoir remplir le bocal à moitié, quoiqu'on dit pas si ils sont gradués

[matthias]

On dispose de trois récipients.
Au départ chaque récipient contient un nombre entier de litres d'un liquide.
Chaque récipient est suffisament grand pour contenir tout le liquide.
La seule opération autorisée est : si un récipient contient n litres, prendre un récipient qui contient au moins n litres, verser n litres dans le premier (le premier contient alors 2n litres).

Montrer que quelle que soit la configuration initiale, on peut toujours vider un des récipients.

Bon vu que ça n'inspire personne ...
Je donne la solution ?

[invitedebe236f]

fait semblant de chercher
faut utiliser les theoreme de bezout ?

[matthias]

fait semblant de chercher
faut utiliser les theoreme de bezout ?

Euh non, pas besoin.

Bon, alors un gros indice.
On considère que les volumes initiaux sont : A, B et C
On prends :

Division euclidienne de B par C : B = qC + r (r<C)

Il existe une série de manipulations pas très compliquées qui permettent d'obtenir un volume r dans le récipient dont le volume initial est B.

[Evil.Saien]

Moi j'ai reflechie a ta question, mais je trouve que c'est pas si simple que ca...
Si on part avec a<b<c (on écarte d'emblée les égalités sinon c'est fini) On note le triplet a ; b ; c
B -> A => 2a ; b-a ; c
Et ensuite on est obligé de considérer plusieurs cas:
est-ce que 2a < b-a ?? 2a < c ??
Donc a chaque fois diverses possibilités sont a prendre en considérations et on arrive vite a une sorte d'arbre, peut-etre que ca marche, mais c'est beaucoup trop long a faire...

Mais bon, j'ai fait chauffer mon petit cerveau dans le vide et suis pressé de connaitre la méthode simple !

++

[matthias]

Moi j'ai reflechie a ta question, mais je trouve que c'est pas si simple que ca...

J'avoue

Si on part avec a<b<c (on écarte d'emblée les égalités sinon c'est fini)

Tu aurais pu prendre le même ordre que moi ...

Mais bon, j'ai fait chauffer mon petit cerveau dans le vide et suis pressé de connaitre la méthode simple !

Bon, bon, d'accord.

Je repars donc avec des contenances initiales A, B et C telles que:

Comme tu le dis on pourrait prendre des inégalités strites, mais ça ne change rien à la méthode que je vais expliquer, et les inégalités larges permettent de montrer que cette méthode n'est pas optimale (si quelqu'un connaît une méthode optimale, je suis preneur).

On s'impose de ne faire que des transvasements de A vers C, ou de B vers C, ce qui fait que le volume de C double à chaque étape.

Posons pour l'étape n (on commence à 0):
si le transvasement se fait de A vers C
si le transvasement se fait de B vers C

On suppose bien sûr pour l'instant que les contenances initiales de A et B étaient suffisantes pour effectuer ces transvasements.

Le volume qui reste dans B après l'étape n est:


Si maintenant on considère la division euclidienne suivante:
où r < C
Et l'écriture de q en base 2 (c'était pourtant simple ):


tout devient plus simple ....
On veut imposer n = N et = pour tout i.
Il suffit pour cela d'effectuer les opérations jusqu'à l'étape N, en transvasant de A dans C si = 0, et de B dans C si = 1 (pour toutes les étapes i bien sûr).

On arrive donc à obtenir un volume de B - qC = r dans le récipient dont le volume initial était B.

Comme r < C, on a obtenu un volume minimal plus faible que celui de la configuration initiale, et on peut donc recommencer jusqu'à un volume nul.

Maintenant il suffit de prendre A = B > C > 0 pour voir que cette méthode n'est pas optimale.

Voilà, voilà, j'espère que j'ai été clair et que je n'ai pas écris de bétises.

[Evil.Saien]

Un truc me chiffone dans cette solution...
On suppose A>B>C tout au long du procédé !
Et comme de part hasard lors du dernier transvasement B<C !
Il y a quand meme beaucoup de suppositions faites, et j'avoue etre un peu décu !
De plus,

Comme r < C, on a obtenu un volume minimal plus faible que celui de la configuration initiale, et on peut donc recommencer jusqu'à un volume nul.

Je suis moyennement convaincu par cet argument:
on arrive a un moment ou A>B>C
On verse B dans C
On trouve alors A>2C>B-C=r
Donc, si maintenant on refait le procédé dans le sceau B, on a:
on verse A (ou C) dans B
On se retrouve avec A-B+C ; 2C; 2B - 2C
On verse C dans B
A-B+C ; 2C - 2B + 2C ; 4B - 4C
Manifestement on sait que B>C et que B < 2C
2C - 2B + 2C - 4B - 4C = -6B <0
Ainsi il n'est plus possible de transvaser C -> B et le procédé s'arrete avant la fin...
On sait également que 4C - 2B = 2(2C - B) qui risque d'etre plus grand que r... Dans ce cas il n'y a pas eu de réduction de volume...

Enfin... Je trouve ce problème bien marrant ! Enoncé très simple et pourtant loin d'etre trivial (pour moi)

[matthias]

Un truc me chiffone dans cette solution...
On suppose A>B>C tout au long du procédé !
Et comme de part hasard lors du dernier transvasement B<C !
Il y a quand meme beaucoup de suppositions faites, et j'avoue etre un peu décu !

Non, on ne suppose pas A > B > C tout au long du procédé. Et on ne fait aucune supposition particulière. Par contre je me suis peut-être mal expliqué.
La démarche consiste simplement à montrer que quelle que soit la configuration de départ dans laquelle aucun récipient n'est vide (appelons N, le minimum des trois volumes initiaux), il est possible d'obtenir une nouvelle configuration où le nouveau minimum vérifie n < N.
C'est ceci que j'ai décrit dans le post précédent (on avait N = C, n = r) et je vais revenir sur un point. Il est évident cependant, qu'une fois ceci démontré, le problème est fini (si n > 0, on recommence, suite strictement décroissante d'entiers ...)

Maintenant, juste une petite précision.
Quand on fait les transvasements de B vers C, et A vers C:
B = qC + r

avec qN = 1
quantité transvasée de B vers C = qC = B - r <= B
quantité transvasée de A vers C = ((2^N+1 -1) - q)C
Or q >= 2^N donc ((2^N+1 -1) - q)C < qC <= B <= A
Donc tous les transvasement envisagés étaient possibles.

[Evil.Saien]

On va prendre un exemple pour voir si j'ai bien compris.
Soit A=15, B=13, C=1.
A -> C => A=14 B=13 C=2
B -> C => A=14 B=11 C=4
A -> C => A=10 B=11 C=8
B -> C => A=10 B=3 C=16

Boucle terminée.
Pourtant on a pas diminué le 1 initial !

[matthias]

On va prendre un exemple pour voir si j'ai bien compris.
Soit A=15, B=13, C=1.
A -> C => A=14 B=13 C=2
B -> C => A=14 B=11 C=4
A -> C => A=10 B=11 C=8
B -> C => A=10 B=3 C=16

Boucle terminée.
Pourtant on a pas diminué le 1 initial !

Si tu as bien lu, on ne fait pas les transvasements au hasard ...
A=15, B=13, C=1
B = 13xC + 0 (q=13)
En binaire 13 s'écrit: 1101, ce qui donne la séquence:
B->C => A=15, B=12, C=2
A->C => A=13, B=12, C=4
B->C => A=13, B=8, C=8
B->C => A=13, B=0, C=16
miracle
Le reste était 0, donc on ça marche en une boucle.
On prend l'écriture binaire de q, dans l'ordre des puissances croissantes, si on a 1 on fait B->C, si on a 0, on fait A->C

Un autre exemple en 2 boucles.
A=15, B=13, C=2
B=6C+1
En binaire 6 s'écrit: 110, ce qui donne la séquence:
A->C => A=13, B=13, C=4
B->C => A=13, B=9, C=8
B->C => A=13, B=1, C=16
On a 1 comme minimum, c'était bien le reste de la division euclidienne.
On remet par ordre décroissant (on renomme).
A=16, B=13, C=1
B=13C+1
13 -> 1101
B->C => A=16, B=12, C=2
A->C => A=14, B=12, C=4
B->C => A=14, B=8, C=8
B->C => A=14, B=0, C=16

J'avais vraiment du mal expliquer
C'est plus clair maintenant ?

[Evil.Saien]

Ah ok, c'est tout bon

[matthias]

Ah ok, c'est tout bon

Maintenant côté optimalité, on est loin.
L'exemple en 2 boucles était faisable en 2 transvasements