Casse-tête: trois barriques, en vider une (1998-08-23)

In article <01bdce90$bcab5740$LocalHost@dell>, Laurent Morel wrote:

> Trois barriques assez grandes contiennent chacune un volume
> d'eau qui s'exprime par un nombre entier.
> On peut transvaser l'eau d'une barrique dans une autre, mais
> dans une quantité égale à celle que la barrique _destination_
> contient déjà (l'opération peut être répétée autant de fois
> que nécessaire).

> Montrer qu'on peut vider une des barriques.

Voici ma solution. J'espère qu'il n'y a pas d'erreur...
Ceux qui veulent chercher peuvent s'arrêter de lire tout de suite.

[SPOILER] [SPOILER] [SPOILER] [SPOILER] [SPOILER] [SPOILER] [SPOILER]

Un transvasement, revient à faire la transformation suivante sur deux
des nombres x et y tels que x <= y: (x,y) -> (2x,y-x). Notons qu'il
s'agit d'une multiplication par 2 modulo x+y, et que la somme ne change
pas.

S'il y a exactement 2 nombres impairs, on fait la transformation sur
ces 2 nombres et on se retrouve avec 3 nombres pairs.

S'il y a 3 nombres pairs, on se ramène au même problème en divisant
tout par 2.

S'il y a 3 nombres impairs, on fait une transformation quelconque, et
on se retrouve avec un seul nombre impair.

[1]
Donc on suppose qu'il y a exactement un nombre impair. On considère les
deux autres nombres x et y. Leur somme est de la forme n * 2^k, où n
est un nombre impair. On fait k fois la transformation sur ces 2 nombres
et on se retrouve avec 2 multiples de 2^k: i * 2^k et p * 2^k, où i est
impair et p est pair (i + p = n). Si p = 0, c'est terminé. Sinon...

On a donc un triplet de la forme: (x = i*2^k, y = (j*2^h)*2^k, z) où
_ i, j, k, h, z sont des entiers positifs;
_ k >= 1;
_ i, j, z sont impairs.

Soit r tel que 2^r = 1 mod (y+z), qui existe puisque y+z est impair.
On fait r-h fois la transformation sur y et z, et on se retrouve avec:
(i*2^k, y' = j*2^k, z') avec z' impair puisque y' est pair et la somme
est impaire. Et on recommence en [1].

Comme à chaque itération le nouveau k est strictement supérieur à
l'ancien (puisque i et j sont impairs), et que la somme totale des
3 nombres ne change pas, le processus se termine.