Tours de Hanoï

Le problème original

FIG. 6.2 – Tours de Hanoï : le problème classique

Problème

Ce problème a été inventé par le mathématicien Edouard LUCAS, d’après une légende hindoue. Selon cette légende, des moines sont gardiens de trois tours. 64 disques d’or concentriques, de plus en plus petits, sont empilés dans une des tours. Les moines doivent les transférer dans une autre tour, avec une règle unique : aucun disque ne doit être posé sur un plus petit. Quand il auront terminé, ce sera la fin du monde.

Une autre légende assure que ce puzzle était utilisé dans un temple pour la discipline mentale des aspirants à l’éveil. . . C’est plutôt dans cette optique que nous l’utiliserons aussi !

Régles

• 3 poteaux ;
• un certain nombre de disques ;
• un déplacement à la fois ;
• aucun disque ne peut être posé sur un disque plus petit.

Résolution

Ce problème a toujours une solution. Il faut pour cela utiliser la troisième tour, comme lieu de stockage temporaire. Soit U le nombre de coups, n le nombre de disques, on calcule U par : U = 2ⁿ - 1.

Ce qui donne pour résultats :

Disques	Nombre de coups
1	1
2	3
3	7
4	15
5	31
...	...
64	18 446 744 073 709 551 615

À raison d’un coup par seconde, il faudra effectivement à nos pauvres moines quelques cinq millions de millénaires pour transférer les 64 disques...

Plus rapidement, avec trois disques :

FIGURE

Proposition de démarche

Il n’est évidemment pas possible de modéliser le problème à l’école primaire et encore moins maternelle ! Néanmoins il permet d’aborder d’intéressantes notions d’algorythmique, notamment grâce à la version simplifiée de GCompris. La manipulation est une phase importante, avant d’aborder la version écran.

Matériel requis

On peut fabriquer facilement un jeu de tours de Hanoï classique en mousse (papèteries spécialisées), voire en bois (avec une scie à cloche). On trouve facilement dans les magasins de jouets, des anneaux gigogne pour bébés, tout à fait adaptés à notre usage.

Mais GCompris proposant aussi une version simplifiée en utilisant des couleurs plutôt que des tailles différentes, on peut très bien utiliser un jeu de grosses perles. Il ne faut fabriquer alors que le support des tours. On peut aussi utiliser du matériel du commerce tel que les abaques Asco™. Une autre possibilité sympathique est d’utiliser des épingles à linge de couleur, à condition de veiller àa ce que l’enfant ne décroche que les pinces normalement accessibles.

Activités

Activité	Objectifs	Déroulement	Évaluation
En rang ! (2)	Comparer, classer et ranger des objets selon leur taille, leur masse ou leur contenance.	On dispose de trois bancs perpendiculaires au mur, dont l’extrémité touche mur. Les enfant se rangent du plus petit au plus grand, le plus grand contre le mur. Ils doivent reconsituer la même disposition sur le deuxième banc, avec les règles suivantes : on ne double pas ; on sort par l’extrémité libre du banc ; aucun enfant ne peut se placer devant un plus petit que lui. Commencer par deux, puis trois enfants. Ne pas dépasser 4.	Par le groupe
Perles	Savoir reproduire l’organisation dans l’espace d’un ensemble limité d’objets (en les manipulant, en les représentant).	Reproduire une séquence de perles donnée à partir des perles disposées sur trois tiges : on déplace une perle à la fois ; on ne garde pas de perle dans la main, ni sur la table. Attention à ce que la manipulation soit effectivement possible : veiller à ce que les perles du modèle soient effectivement dans le jeu.	Séquence identique à l’original.
GCompris - Tours de Hanoï simplifiées	Id.	Utilisation de GCompris par groupe de deux élèves, puis individuellement.	Fiche de suivi ou évaluation intégrée au logiciel (V 7.0)
Tours de Hanoï classiques	Id.	Résoudre le problème classique avec trois, voire quatre anneaux.	Réussite du problème. Il est intéressant de savoir si le résultat est obtenu après tâtonnements ou bien directement par une démarche algorythmique maîtrisée (au bout de quelques essais).
Tours de Hanoï virtuelles avec GCompris	Id.	Utilisation de GCompris par groupe de deux élèves, puis individuellement.	Fiche de suivi ou évaluation intégrée au logiciel (V 7.0)
Tours de Hanoï - Papier découpé	Id.	Une fois le principe du jeu acquis, il est possible de demander aux enfants de reconstituer les étapes de la résolution du problème avec trois disques, à l’aide de bandes de papier ou en coloriant les disques vides (cf. fiche d’activité suivante).	Réussite de la fiche d’activité.