Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 22-01-2012 19:47:58

racine
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1224

Mesuurer 1 cl (cas général)

L'énigme de Titoufred (mesurer 1 cl, http://www.prise2tete.fr/forum/viewtopi … 1#p139171) me fait me poser une question dont je n'ai pas la réponse.

Peut-on toujours avec deux récipients de contenance donnée a cl et b cl, obtenir 1 cl? Et dans le cas contraire, quelles conditions doivent respecter les deux récipients?

On supposera a et b entiers.

Je précise les conditions suite à une remarque de Vasimolo. On dispose d'un robinet et de seulement deux récipients.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 22-01-2012 19:51:23

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Mesurer 1 cl (ccas général)

Une condition nécessaire est que a et b soient premiers entre eux smile

C'est certainement suffisant si on accepte l'utilisation d'autres récipients pour servir" d'escale" .

Vasimolo

 #3 - 22-01-2012 20:18:14

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Mesurer 1 cl (cas généal)

Si a et b sont premiers entre eux, oui on peut. Le problème se ramène à une équation de Bezout. Résoudre cette équation ,c'est d'ailleurs trouver la quantité d'eau qui sera nécessaire.

 #4 - 22-01-2012 20:31:42

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Mesurer 1 cl (cas génréal)

Avec des contenances x et y , il faut au moins que l'équation ax + by = 1 ait une solution entière à mon avis.

Ca exclut par exemple le cas de 2 contenances paires.

 #5 - 22-01-2012 21:27:51

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Mesurer 1 cl (cas généra)

La quantité minimum qu'on peut trouver est le pgcd de a et b.
Si a et b sont premiers entre eux, alors oui on pourra obtenir 1cl, sinon on ne pourra pas smile

Je réfléchis à une démo rigoureuse, parce que là pour l'instant c'est + intuitif qu'autre chose lol

 #6 - 22-01-2012 21:37:50

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Mesurer 1 cl (cas généra)l

Réponse instinctive: il faut pgcd(a,b)=1

Approche demonstrative
soit k le pgcd, les recipients ont une contenance de kx et ky.
la différence des deux est k(x-y) etc. La plus petite quantité qui peut être obtenu est k.


The proof of the pudding is in the eating.

 #7 - 23-01-2012 00:56:51

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Mesurer 1 cl (cas énéral)

Je pense que si les recipients sont tous les 2 de contenance pair, tu n'auras jamais 1cl.

 #8 - 23-01-2012 09:31:48

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Mesurer 1 cl (as général)

Avec deux récipients de capacités A et B, il est impossible d'obtenir un volume strictement positif qui soit inférieur à d=PGCD(A,B).

Démonstration par invariant: les 2 récipients contiennent toujours une quantité de liquide multiple de d. C'est le cas quand ils sont vides tous les deux.
On notera une configuration où les  récipients contiennent A' et B' de la manière suivante: (A', B')
Depuis (A', B'), je peux:
- vider un récipient et passer en (0, B') ou en (A', 0)
- remplir un récipient entièrement depuis le robinet et passer en (A, B') ou en (A', B)
- transvaser entièrement un récipient dans l'autre (si c'est possible) et passer en (0, A'+B') ou en (A'+B', 0)
- transvaser récipient dans l'autre jusqu'à le remplir (si c'est possible) et passer en (A'-B+B', B) ou en (A, B'-A+A')
Comme A, B, A', B' et 0 sont des multiples de d; on a donc prouvé notre invariant.

On a donc montré qu'on ne peut pas avoir de volume entre 0 et PGCD(A,B)
On peut bien sûr avoir 0, montrons qu'on peut aussi avoir PGCD(A,B).

Tout d'abord, si A et B sont premiers entre eux (on notera A<B); on peut avoir 1cl.
En remplissant A et en le transvasant dans B jusqu'à le remplir; il me reste dans A une certaine quantité A'.
En répétant cette étape, il me reste 2A' (modulo A bien sûr), etc...
Or A' et A sont premier entre eux; en effet A'+B est un multiple de A (c'est ce qu'il me reste après avoir complété B en n'utilisant que des A) et A et B sont premiers entres eux
Du coup, la classe de A' engendre le groupe (Z/AZ, +)
Pour les non-initiés, ça veut juste dire que modulo A; en additionnant A' plusieurs fois; on trouve toutes les valeurs comprises entre 0 et A-1; donc 1 aussi.

On peut donc obtenir 1cl avec deux récipients si A et B sont premiers entre eux.
S'ils ne le sont pas, alors d=PGCD(A,B) donc A=m*d et B=n*d. En prenant comme unité non plus le centilitre mais le "d centilitres", on peut appliquer le même raisonnement: un récipient n et un autre m avec n et m premier entre eux: on peut donc obtenir une unité, soit d centilitres.

Conclusion: soient 2 récipients de capacités respectives A et B; le plus petit volume non nul qu'on puisse mesurer est PGCD(A,B)

 #9 - 23-01-2012 11:09:12

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

Mesurer 1 cl (cs général)

Je dirais qu'il faut que a et b soient premiers entre eux.
En effet sinon toutes les quantités que l'on peut mesurer avec l'un ou l'autre plein ou par sommes ou différences sont toutes multiples du PGCD.
D'autre part, pour prouver que c'est facile, j'ai donné la démonstration générale dans l'énigme avec 20 et 33.
Si a et b sont premiers entre eux, b est générateur de [latex](\mathbb{Z}/_{a\mathbb{Z}}, +)[/latex] et donc on arrive à tomber sur 1 modulo a... Voir la démo ici: http://www.prise2tete.fr/forum/viewtopi … 68#p139298

 #10 - 23-01-2012 11:15:01

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Mesurer 1 cl (cs général)

Je dirais "a et b doivent être premiers entre eux", car il est clair, par exemple, qu'avec a et b pairs, on ne peut pas obtenir un volume impair à la fin. De manière générale, on ne pourra pas obtenir de volumes qui ne soient pas de la forme au+bv, donc pour pouvoir obtenir 1cL, on veut a et b premiers entre eux.

La réponse à la question "peut-on obtenir tous les au+bv inférieurs ou égaux à max(a,b) avec deux récipients de volumes a et b ?" m'échappe. Si oui, alors la condition nécessaire énoncée ci-dessus est suffisante.


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #11 - 23-01-2012 11:22:38

racine
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1224

mesurer 1 cl (czs général)

@MthS-MlndN : la précision sur les deux récipients a été apportée à chaud suite à une remarque de Vasimolo. A la lecture des réponses, ça n'a pas d'importance.

 #12 - 23-01-2012 19:53:57

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

mesurer 1 cl (cas générak)

C'est marrant je me suis posé la même question quand j'ai vu le problème initial, et j'ai juste intuité le résultat, là ça permet de pousser le raisonnement plus loin smile

Si a et b ne sont pas premiers entre eux, alors les quantités minimum que peuvent contenir les 2 récipients sont des multiples du pgcd de a et b.
En effet, on peut définir un invariant : les quantités dans les 2 récipients sont des multiples du pgcd de a et b.
. c'est le cas au début (0cl dans les 2 récipients)
. si on a une quantité dans les 2 récipients qui est multiple du pgcd de a et b, alors chaque récipient peut encore accueillir un multiple de ce pgcd :
  - si on remplit l'un des 2 (ou les 2, même si c'est idiot), on garde un multiple.
  - si on verse le contenu de l'un dans l'autre (jusq'au maximum, sinon on ne connait plus les quantités exactes), c'est toujours le cas aussi.
Donc on ne pourra jamais arriver à une quantité de 1cl si a et b ne sont pas premiers entre eux.

En revanche, quand a et b sont premiers entre eux, c'est possible, grâce à Bezout :
Il existe x et y, 0<x<b et 0<y<a tels que :
ax-by=1
Il suffit alors de remplir A, de le verser dans B, de vider B quand il est rempli, et de vider A dans B tant qu'il n'est pas vide, alors on arrivera au bout de x remplissages de x à 1cl.
On peut même optimiser :
(a-y)b-a(b-x)=1
Si b-x > (a-y), on préférera remplir B et le vider dans A (on fera moins d'opérations, fainéants que nous sommes !)

Dans l'exemple avec 33 et 20 :
5*20 - 3*33 = 1
C'est mieux que 17*33 - 28*20 = 1, comme j'avais fait au début, je m'étonnais de pas tomber rapidement sur 1cl, forcément avec 17 remplissages de canettes big_smile

 #13 - 24-01-2012 01:42:27

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

Mesuurer 1 cl (cas général)

si a et b ne sont pas premiers entre eux, toutes les opérations de remplissages / vidages se feront en multiples de leur diviseur commun.

si a et b sont premiers, alors, il existe m et n tels que a m - b n = 1 (en inversant les rôles de a et b si besoin).
On procède alors de la sorte :
On remplit A, on le verse dans B jusqu'à ce que B soit plein (et alors on le vide) ou A vide (et alors on le remplit). Et on continue.
Après m remplissage de A et n remplissage de B, il restera exactement 1 dans A.

 #14 - 24-01-2012 12:14:04

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

eMsurer 1 cl (cas général)

Après une petite réflexion, j'en suis arrivé à un résultat un peu plus sympathique.

Tout d'abord, l'invariant dont je parlais plus haut montre clairement que toute quantité mesurée est un multiple de PGCD(A,B).

Autre point beaucoup plus intéressant, j'ajoute au problème les contraintes suivantes:
- je ne peux remplir un récipient que s'il est entièrement vide
- je ne peux vider un récipient que s'il est entièrement plein
On peut alors montrer, très simplement, qu'on peut obtenir les mêmes solutions que sans ces contraintes. En effet, on ne peut ajouter ou soustraire au volume total que a ou b.
Dans ce cas, le théorème de Bachet-Bézout nous dit qu'il existe toujours 2 entiers x et y tels que xA+bY = PGCD(A,B)
Par exemple, si x est positif et y négatif; cela signifie: "remplir A x fois; qu'on transvase dans B à chaque fois. On videra B dès qu'il est plein, y fois"
Bien entendu, n*x et n*y nous donnera n*PGCD(A,B) pour tout n (sous réserve bien sûr que n*PGCD(A,B) soit inférieur à A ou B)

 #15 - 24-01-2012 21:51:23

gilles355
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 416

Mesurre 1 cl (cas général)

Ca me fait penser à la suite de Syracuse:
"Prenez un nombre s'il est pair diviser le par 2, sinon multiplier le par 3 et ajouter lui 1"
Dans cette célèbre suite pour n'importe quel nombre pris on retombe avec plus ou moins d'étape à 1.
A l'heure actuelle aucun homme n'a réussi à le prouver.

Je pense que ton problème s'en rapproche, donne moi deux quantité de récipient et j'y arriverai, demande moi de prouver que c'est tout le temps vrai...

 #16 - 25-01-2012 08:51:59

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

Mesurer 1 cl (caas général)

On peut obtenir 1cl si et seulement si a et b sont premiers entre eux.
On convient que le récipient 1 est de a cl et le récipient 2 de b cl.

Prouvons que la condition est nécessaire.
En effet soit k un diviseur commun à a et b.
Alors par récurrence on montre aisément que les 2 récipients contiennent des multiples de k. Donc si l'on peut obtenir 1cl, on a k divise 1, c-à-d k=1.

Prouvons que la condition est suffisante.
a et b sont premiers entre eux donc ils satisfont à une relation de Bezout au+bv=1 avec u,v  entiers relatifs. On a donc aussi a(u+rb)+b(v-ra)=1 pour tout entier relatif r. Par suite il existe k entier >=1 tel que ka=1 modulo b.
La  méthode (qui n'est pas en général la plus rapide) consiste à verser continuellement le récipient 1 dans le récipient 2. Quand le récipient 2 est plein, on le vide. Quand le récipient 1 est vide, on le remplit avec l'eau du robinet.

 #17 - 25-01-2012 19:51:26

racine
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1224

Mesurer 1 cl (ca général)

Bon, ben tout le monde est d'accord. Trois façons de dire la même chose
- a et b premiers entre eux
- pgcd(a,b)=1
- ax + by = 1

Par contre, je regrette d'avoir posé la question tout de suite sans prendre le temps d'y réfléchir. Du coup, j'ai juste regardé les réponses.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete