La tour de Hanoï est un jeu de réflexion imaginé par le

mathématicien Édouard Lucas. Sur le plateau de jeu, il y a trois piquets. Des disques sont empilés par ordre de taille décroissante sur un des piquets (le plus grand disque étant en dessous). L'objectif est de dépla- cer la pile de disques du premier piquet au dernier piquet. Il faut déplacer un seul disque à la fois et ne jamais poser un disque sur un disque plus petit que lui. Le déplacement d'un disque compte comme un coup.

1. Déterminer le nombre minimal de coups à effectuer pour déplacer une pile de deux disques du premier au dernier piquet.

2. Déterminer le nombre minimal de coups à effectuer pour déplacer une pile de trois disques du premier au dernier piquet.

3. On note u le nombre minimal de coups à effectuer pour déplacer une pile de n disques du premier au dernier piquet. Donner la valeur de u₁, u₂ et u¸.

4. L'objectif est de trouver une relation entre u n+1 Pour cela, on considère le déplacement d'une pile de n + 1 disques du premier au dernier piquet. et un

a) Quel est le nombre minimal de coups à effectuer pour rendre le plus grand disque accessible? b) Combien de coup(s) faut-il ensuite pour déplacer le plus

grand disque sur un autre piquet?

c) Quel est le nombre minimal de coups à effectuer ensuite pour reformer la pile ?

d) En déduire une relation entre u n+1 et un 5. À l'aide de la calculatrice, déterminer le nombre minimal de coups pour déplacer une pile de 15 disques. svp