Forum de mathématiques - Bibm@th.net

Camille23

Invité

Les vases communicants de Freddy

Bonjour,

Solution simple à ce problème posé en 2011 par freddy : Solution éjà exposée ou trouvée ?

Face à nous, trois urnes transparentes A, B et C.
Dans la première A se trouvent 3n boules, les deux autres sont vides.
Je dois, en n étapes, arriver à avoir n boules dans chaque urne avec la règle de gestion suivante : à chaque étape p, je peux déplacer exactement p boules d'une urne vers une autre.

Des solutions pour N de 5 à 14 existent et peuvent être produites "à la main".
Pour tout N>14 :
On peut utiliser la division euclidienne N=3q+r pour réduire N à n=q (avec r  égal à 0,1 ou 2)
Si on trouve une solution pour n, il suffit de continuer à effectuer des transferts de valeurs
(n+1) à (3n+r) pour avoir une solution pour (3n+r).
Après un nombre fini d'itérations la division euclidienne donne une valeur 4<n<15 avec un r<3.

Bien sûr, en choisissant ce dernier n pour  commencer les transferts, la première urne contiendra 3N et non pas seulement 3n boules,

Codes :xy signifie transfert de  x vers y ;  ab=1, ba=-1, ac=2, ca=-2, bc=3, cb=-3

Démonstration formelle pour les séquences de n à 3n+r
r=0 :
[tex]\begin{array} {ccccccccccccc|}\\code & transfert & A & B & C & \\Début && 7n & n & n & \text{fin de séquence n avec A ajusté car 9n 0 0 avant le tout premier transfert} \\2 & n+1 & 6n-1 & n & 2n+1 & & \\\text{(n-2) fois} & & 6n-1 &2 & 3n-1 & \text{ transferts de n+2 à n+2+[2(n-2)] soit de n+2 à 3n-2} \\1&3n-2&3n+1&3n&3n-1 \\-2&3n-1&6n&3n&0 \\2&3n&3n&3n&3n \end{array}[/tex]
il est évident qu'il n'y a pas de dépassement  <0 ou >9n

r=1 :
[tex]\begin{array} {ccccccccccccc|}\\code & transfert & A & B & C & \\Début && 7n+3 & n & n & \text{fin de séquence n avec A ajusté car 9n+3 0 0 avant le tout premier transfert} \\2 & n+1 & 6n+2 & n & 2n+1 & & \\ \text{(n-1) fois} & & 6n+2 &1 & 3n & \text{ transferts de n+2 à n+2+[2(n--1)] soit de n+2 à 3n} \\-3&3n&6n+2&3n+1&0 \\2&3n+1&3n+1&3n+1&3n+1\end{array}[/tex]
il est évident qu'il n'y a pas de dépassement  <0 ou >9n+3

r=2 :
[tex]\begin{array} {ccccccccccccc|}\\code & transfert & A & B & C & \\Début && 7n+6 & n & n & \text{fin de séquence n avec A ajusté car 9n+6 0 0 avant le tout premier transfert} \\2 & n+1 & 6n+5 & n & 2n+1 & & \\ \text{(n-1) fois} & & 6n+5 &1 & 3n & \text{ transferts de n+2 à n+2+[2(n--1)] soit de n+2 à 3n} \\-2&3n&9n+5&1&0 \\1&3n+1&6n+4&3n+2&0 \\2&3n+2&3n+2&3n+2&3n+2 \end{array}[/tex]
il est évident qu'il n'y a pas de dépassement  <0 ou >9n+6