Répondre à la discussion
Affichage des résultats 1 à 24 sur 24

un peu de réflexion



  1. #1
    soulcrusher

    un peu de réflexion


    ------

    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

    -----

  2. Publicité
  3. #2
    jess n'ohm

    Re : un peu de réflexion

    Un Classique !

    J'ai, mais je vous demande de me croire sur parole, sinon il n'y aurait plus de réflexion.
    "Trouver quelque chose ?... Mais c'est déjà fait" (turk et de groot)

  4. #3
    matthias

    Re : un peu de réflexion

    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.

  5. #4
    matthias

    Re : un peu de réflexion

    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.

  6. A voir en vidéo sur Futura
  7. #5
    jess n'ohm

    Re : un peu de réflexion

    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 !
    "Trouver quelque chose ?... Mais c'est déjà fait" (turk et de groot)

  8. #6
    matthias

    Re : un peu de réflexion

    Citation Envoyé par jess n'ohm
    J'avais une autre solution :
    Ta solution est plus rapide (6 étapes, contre 8 pour la mienne). Est-elle optimale ?

  9. Publicité
  10. #7
    jess n'ohm

    Re : un peu de réflexion

    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.
    Dernière modification par jess n'ohm ; 12/04/2005 à 17h28.
    "Trouver quelque chose ?... Mais c'est déjà fait" (turk et de groot)

  11. #8
    soulcrusher

    Re : un peu de réflexion

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

  12. #9
    mayonaise

    Re : un peu de réflexion

    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 2n (b-a) litres dans b, mais rien ne nous indique que dans c on ait 2n (b-a) (ou que dans b on ait 2n (c-a) ) qui me semble être une condition nécessaire au bon fonctionnement du truc muche...
    Impose ta chance, serre ton bonheur, va vers ton risque.
    A te regarder ils s'habitueront. ♂

  13. #10
    matthias

    Re : un peu de réflexion

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

  14. #11
    Evil.Saien

    Re : un peu de réflexion

    J'ai l'impression que ce problème ressemble aux disques de Hanoï...
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  15. #12
    matthias

    Re : un peu de réflexion

    Citation Envoyé par Evil.Saien
    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 ....

  16. Publicité
  17. #13
    heruhur

    Re : un peu de réflexion

    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
    Denver, le dernier dinosaure
    Heruhur, le dieu faucon, prince du soleil

  18. #14
    matthias

    Re : un peu de réflexion

    Citation Envoyé par 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 ?

  19. #15
    cricri

    Re : un peu de réflexion

    fait semblant de chercher
    faut utiliser les theoreme de bezout ?

  20. #16
    matthias

    Re : un peu de réflexion

    Citation Envoyé par cricri
    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.

  21. #17
    Evil.Saien

    Re : un peu de réflexion

    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 !

    ++
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  22. #18
    matthias

    Re : un peu de réflexion

    Citation Envoyé par Evil.Saien
    Moi j'ai reflechie a ta question, mais je trouve que c'est pas si simple que ca...
    J'avoue

    Citation Envoyé par Evil.Saien
    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 ...

    Citation Envoyé par Evil.Saien
    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.

  23. Publicité
  24. #19
    Evil.Saien

    Re : un peu de réflexion

    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)
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  25. #20
    matthias

    Re : un peu de réflexion

    Citation Envoyé par 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 !
    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 = ((2N+1 -1) - q)C
    Or q >= 2N donc ((2N+1 -1) - q)C < qC <= B <= A
    Donc tous les transvasement envisagés étaient possibles.

  26. #21
    Evil.Saien

    Re : un peu de réflexion

    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 !
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  27. #22
    matthias

    Re : un peu de réflexion

    Citation Envoyé par 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 !
    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 ?

  28. #23
    Evil.Saien

    Re : un peu de réflexion

    Ah ok, c'est tout bon
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  29. #24
    matthias

    Re : un peu de réflexion

    Citation Envoyé par Evil.Saien
    Ah ok, c'est tout bon


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

  30. Publicité

Discussions similaires

  1. reflexion
    Par medort dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 16/05/2007, 18h50
  2. Quelqu'un peu m'expliquer un peu les métiers de l'infographie
    Par gaiaone dans le forum Orientation après le BAC
    Réponses: 0
    Dernier message: 12/02/2007, 17h15
  3. Reflexion
    Par pmdec dans le forum Physique
    Réponses: 7
    Dernier message: 04/02/2006, 15h28
  4. Réflexion..
    Par ClaudeH dans le forum Science ludique : la science en s'amusant
    Réponses: 9
    Dernier message: 09/05/2005, 23h09