détour de magie
On peut voir cet article comme un clin d'oeil à celui-ci. Comme lui, il fait référence à un fameux problème. Comme lui, il fait référence à un problème de tour. Comme lui, la notion de récurrence aura sa place.
Ici on s'intéresse au problème de la tour de Hanoï et on exploitera la récurrence pour aboutir à une procédure récursive abracadabrantesque.
On dispose d'une unique tour composée de n étages initialement superposés sur le site I. Le but du jeu est de la déplacer sur le site final F en s'aidant du site auxiliaire A.
Les règles du jeu : chaque étage possède une dimension (réelle) qui lui est propre si bien que, pour assurer la stabilité de deux étages consécutifs, c'est toujours l'étage qui a la plus petite dimension qui est posé sur l'autre. Initialement chaque paire d'étages consécutifs est stable. De plus, chaque étage est transportable d'un site à un autre à deux conditions
[(I : 4>3>2>1)(A:)(F:)]
2 choix : [(I : 4>3>2) (A : 1) (F:)] ou [(I : 4>3>2) (A:) (F : 1)]
Si on choisit le premier : [(I : 4>3) (A : 1) (F : 2)]
2 choix : [(I : 4>3>1) (A :) (F : 2)] ou [(I : 4>3) (A :) (F : 2>1)]
Si on choisit le second : [(I : 4) (A :3) (F : 2>1)]
2 choix : [(I : 4>1) (A :3) (F : 2)] ou [(I : 4) (A :3>1) (F : 2)]
Si on choisit le premier : [(I : 4>1) (A :3>2) (F : )]
2 choix : [(I : 4) (A :3>2>1) (F : )] ou [(I : 4) (A :3>2) (F : 1)]
La méthode semble difficile à trouver !
Toutefois, en observant le premier choix de la dernière alternative, il est judicieux de réécrire le problème de départ
[(I : 4>3>2>1)(A:)(F:)] vers [(I : )(A:)(F:4>3>2>1)]
en 3 parties :
[(I : 4>3>2>1)(A:)(F:)] vers [(I : 4)(A:3>2>1)(F:)]
[(I : 4)(A:3>2>1)(F:)] vers [(I : )(A:3>2>1)(F:4)]
[(I : )(A:3>2>1)(F:4)] vers [(I : )(A:)(F:4>3>2>1)]
Ici finit la partie jeu et commence la partie magie.
On admet que cette décomposition en 3 est généralisable : on compte neuf cycles après les douze coups de minuit avant d'ouvrir le grimoire en son dernier tiers, puis à la lueur d'un cierge, on trace à l'encre de sève de mandragore les signes de la formule
(abra c d b r) = (abra c-1 d r b) [d-b] (abra c-1 r b d)
Cette formule s'applique (quelque soit n) en la développant n fois à partir de (abra n I F A) et en remplaçant (abra 1 x y z) par [x-y] :
(abra 4 I F A)
= (abra 3 I A F) [I-F] (abra 3 A F I)
=(abra 2 I F A) [I-A] (abra 2 F A I) [I-F] (abra 2 A I F) [A-F] (abra 2 I F A)
=(abra 1 I A F) [I-F] (abra 1 A F I)[I-A] (abra 1 F I A) [F-A] (abra 1 I A F) [I-F] (abra 1 A F I) [A-I] (abra 1 F I A)[A-F] (abra 1 I A F) [I-F] (abra 1 A F I)
=[I- A] [I-F] [A- F] [I-A] [F- I] [F-A] [ I- A] [I-F] [A- F] [A-I] [F- I][A-F][ I- A] [I-F][ A- F]
Les 2n-1=15 mouvements du résultat sont à lire de gauche à droite et sont de la forme [ site où on prélève - site où on transporte ].
Ici on s'intéresse au problème de la tour de Hanoï et on exploitera la récurrence pour aboutir à une procédure récursive abracadabrantesque.
On dispose d'une unique tour composée de n étages initialement superposés sur le site I. Le but du jeu est de la déplacer sur le site final F en s'aidant du site auxiliaire A.
Les règles du jeu : chaque étage possède une dimension (réelle) qui lui est propre si bien que, pour assurer la stabilité de deux étages consécutifs, c'est toujours l'étage qui a la plus petite dimension qui est posé sur l'autre. Initialement chaque paire d'étages consécutifs est stable. De plus, chaque étage est transportable d'un site à un autre à deux conditions
- il est le dernier sur le site d'où on le prélève
- sa dimension est inférieure à celle du dernier étage du site où on le transporte
[(I : 4>3>2>1)(A:)(F:)]
2 choix : [(I : 4>3>2) (A : 1) (F:)] ou [(I : 4>3>2) (A:) (F : 1)]
Si on choisit le premier : [(I : 4>3) (A : 1) (F : 2)]
2 choix : [(I : 4>3>1) (A :) (F : 2)] ou [(I : 4>3) (A :) (F : 2>1)]
Si on choisit le second : [(I : 4) (A :3) (F : 2>1)]
2 choix : [(I : 4>1) (A :3) (F : 2)] ou [(I : 4) (A :3>1) (F : 2)]
Si on choisit le premier : [(I : 4>1) (A :3>2) (F : )]
2 choix : [(I : 4) (A :3>2>1) (F : )] ou [(I : 4) (A :3>2) (F : 1)]
La méthode semble difficile à trouver !
Toutefois, en observant le premier choix de la dernière alternative, il est judicieux de réécrire le problème de départ
[(I : 4>3>2>1)(A:)(F:)] vers [(I : )(A:)(F:4>3>2>1)]
en 3 parties :
[(I : 4>3>2>1)(A:)(F:)] vers [(I : 4)(A:3>2>1)(F:)]
[(I : 4)(A:3>2>1)(F:)] vers [(I : )(A:3>2>1)(F:4)]
[(I : )(A:3>2>1)(F:4)] vers [(I : )(A:)(F:4>3>2>1)]
Ici finit la partie jeu et commence la partie magie.
On admet que cette décomposition en 3 est généralisable : on compte neuf cycles après les douze coups de minuit avant d'ouvrir le grimoire en son dernier tiers, puis à la lueur d'un cierge, on trace à l'encre de sève de mandragore les signes de la formule
(abra c d b r) = (abra c-1 d r b) [d-b] (abra c-1 r b d)
Cette formule s'applique (quelque soit n) en la développant n fois à partir de (abra n I F A) et en remplaçant (abra 1 x y z) par [x-y] :
(abra 4 I F A)
= (abra 3 I A F) [I-F] (abra 3 A F I)
=(abra 2 I F A) [I-A] (abra 2 F A I) [I-F] (abra 2 A I F) [A-F] (abra 2 I F A)
=(abra 1 I A F) [I-F] (abra 1 A F I)[I-A] (abra 1 F I A) [F-A] (abra 1 I A F) [I-F] (abra 1 A F I) [A-I] (abra 1 F I A)[A-F] (abra 1 I A F) [I-F] (abra 1 A F I)
=[I- A] [I-F] [A- F] [I-A] [F- I] [F-A] [ I- A] [I-F] [A- F] [A-I] [F- I][A-F][ I- A] [I-F][ A- F]
Les 2n-1=15 mouvements du résultat sont à lire de gauche à droite et sont de la forme [ site où on prélève - site où on transporte ].