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.
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.
