bonjour à tous,
voilà :
Un homme se trouve au bord de la mer. Il a deux seaux de volumes de a et de b litre, avec pgcd (a,b) = 1. comment peut-il mesurer exactement un litre d'eau? (sans autre moyen que les deux seaux, mais en connaissant a et b)
facile avec a b connu
mais tu veux qu on demontre toute les solutions ca c est plus dur
je me lance
le truc est de transvaser n fois de a vers b on conside a<b
comme il ont un pgcd de 1 une fois rempli b il va rester dans a soit 1 l soit plus on vide b on vide a dans b et on recommence
hum pas sur que ca marche
Re : énigme (avec pgcd)
J'espère que notre bonhomme sait que grâce au théorème de Bezout, il exite u et v dans Z tels que au+bv=1. Sinon, j'imagine le stress.
Sinon, on peut sûrement trouver un système basé sur l'algorithme d'Euclide mais malheureusement, je suis trop fainéant.
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
nabbla je prefere ta demonstration a la mienne
mais bon moi de toute facon j ai un seau d un litre
et oui le but c'est de démontrer, moi aussi intuitivement j'arrive à voir ce qui ce passe, mais formaliser le problème c'est une autre histoire.
D'après bezout, et quitte à échanger a et b, on a :
a*u = 1 + b*v avec u,v > 0.
Donc n remplit a que l'on vide (éventuellement plusieurs fois) dans b jusqu'à le remplir. Quand b est plein on le vide. On fait cette manoeuvre 'u' fois. Ce qui reste dans a c'est 1 littre !
Oui ça marche.
On peut aussi le voir comme suit:
1 = a*u - b*v
On doit donc remplir u fois a et vider v fois b....
Donc en remplissant b et en le visant dans a, que l'on vide, c'set bien ce qu'on fait!!!
En gros, quand un verre est plein, on le vide; et quand un verre est vide, on le plaint
maintenant peut-on généraliser à obtenir pgcd(a,b) litres. Avec biensur a et b non permiers entre eux.
