Suites : tour de hanoi version 2
dans Arithmétique
Encore moi,
Cette version de la tour de hanoi est posée en exercice dans le livre concrete mathematics de Donald E. Knuth . Le sujet est en anglais.
"Find the shortest sequence of moves that transfers a tower of n disks
from the left peg A to the right peg B, if direct moves between A and B
are disallowed. (Each move must be to or from the middle peg. As usual,
a larger disk must never appear above a smaller one.)"
Le transfer direct du piquet A à B est interdit. Il faut un transfer à un piquet intermédiaire. Trouver le nombre de mouvement le plus court, pour un transfer de n disques.
Après réflexion avec deux disques, je pense qu'il faut $M_n$ = $6_{n-1}$ + 2 mouvements.
Le grand disque bouge deux fois. Et ceux du dessus, 2 fois (un aller), 2 fois (un retour) et enfin 2 fois (un autre aller). Après généralisation à n-1 ca fait donc $M_n$ = $6_{n-1}$ + 2 avec n > 0, $M_0$ = 0. Il ne me restait qu'à résoudre l'équation.
Mais j'ai faussé.
Voilà ce qu'ils trouvent et je ne comprend pas.
If Xn is the number of moves, we have $X_0$ = 0 and $X_n$ = $X_{n-1}$ + 1 +
$X_{n-1}$ + 1 + $X_{n-1}$ when n > 0. It follows (for example by adding 1 to both
sides) that $X_n$ = $3^n$ - 1. (After $\frac{1}{2}X_n$ moves, it turns out that the entire tower
will be on the middle peg, halfway home!)
Merci de votre aide.
Cette version de la tour de hanoi est posée en exercice dans le livre concrete mathematics de Donald E. Knuth . Le sujet est en anglais.
"Find the shortest sequence of moves that transfers a tower of n disks
from the left peg A to the right peg B, if direct moves between A and B
are disallowed. (Each move must be to or from the middle peg. As usual,
a larger disk must never appear above a smaller one.)"
Le transfer direct du piquet A à B est interdit. Il faut un transfer à un piquet intermédiaire. Trouver le nombre de mouvement le plus court, pour un transfer de n disques.
Après réflexion avec deux disques, je pense qu'il faut $M_n$ = $6_{n-1}$ + 2 mouvements.
Le grand disque bouge deux fois. Et ceux du dessus, 2 fois (un aller), 2 fois (un retour) et enfin 2 fois (un autre aller). Après généralisation à n-1 ca fait donc $M_n$ = $6_{n-1}$ + 2 avec n > 0, $M_0$ = 0. Il ne me restait qu'à résoudre l'équation.
Mais j'ai faussé.
Voilà ce qu'ils trouvent et je ne comprend pas.
If Xn is the number of moves, we have $X_0$ = 0 and $X_n$ = $X_{n-1}$ + 1 +
$X_{n-1}$ + 1 + $X_{n-1}$ when n > 0. It follows (for example by adding 1 to both
sides) that $X_n$ = $3^n$ - 1. (After $\frac{1}{2}X_n$ moves, it turns out that the entire tower
will be on the middle peg, halfway home!)
Merci de votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
le $X_n = X_{n-1} + 1 + X_{n-1} + 1 + X_{n-1}$ vient du fait que, pour déplacer une tour de $n$ étages, il faut déplacer une tour de $n-1$ étages de $A$ en $B$, puis bouger le premier étage au milieu, remettre la tour à $n-1$ étages à sa position initiale, placer le premier étage en $B$, puis déplacer une nouvelle fois la tour à $n-1$ étages en $B$.