Zoofast.fr vous connecte avec des experts prêts à répondre à vos questions. Rejoignez notre plateforme de questions-réponses pour recevoir des réponses rapides et précises de la part de professionnels expérimentés dans divers domaines.
Les tours de Hanoi sont un casse-tête du mathémati- cien français Édouard Lucas (1892). Le jeu consiste à transporter trois disques 1, 2, 3 placés par taille décrois- sante du piquet A au piquet C en respectant les règles suivantes :
⚫ on ne déplace qu'un disque à la fois; ⚫ on ne place un disque que sur un autre disque plus grand ou sur un piquet vide.
8
C
1. Résoudre ce casse-tête.
Cela peut être effectué en 7 déplacements. 2. On suppose maintenant que l'on dispose
des
piquets A, B, C mais avec cette fois n disques numéro-
tés 1, 2,...,n (avec n > 1).
On note T, le nombre minimum de coups pour trans- porter la tour de A en C. a) Pour transporter les n disques de A en C, on trans-
porte d'abord les n-1 disques les plus petits en B,
puis le grand disque en C. En déduire une relation de
récurrence entre T, et T, (avec n > 1).
b) Démontrer que la suite (u,) définie pour tout nom-
bren de Navec n = 1par u,, = T, +1 est géométrique.
c) Exprimer T, en fonction de n.
d) Quel est le nombre minimum de coups pour trans-
porter une tour de 10 disques de A en C?
