Réfléchissons un peu ensemble...
Si vous avez bien cherché, vous avez dû trouver le nombre de coups minimum pour déplacer 1, 2, 3 ou 4 disques. Remarquez-vous quelque chose? (Indice : ajoutez 1 à chacun de ces nombres).
Si vous ne remarquez rien, peut-être est-ce parce que vous n'avez pas trouvé le nombre minimum ? Cherchez encore ou si vous êtes prêt à tricher, regardez ici.
Maintenant que vous avez remarqué quelque chose, il faudrait savoir s'il s'agit d'une coincidence ou si ça marche pour un nombre plus grand de disques.
Pour cela, nous allons procéder par induction, i.e. faire une démonstration par récurrence : Si l'on sait que le nombre minimum de coups pour déplacer une pile de n disques est C, combien en faudra-t-il pour une pile de (n+1) disques ?
On sait que l'on peut déplacer les n disques du haut vers la position intermédiaire en C coups. Maintenant, il est possible de déplacer le disque du bas sur la position finale. Enfin, il faut remettre les n disques du haut par-dessus. Cela prend encore C coups. Ainsi, on peut bouger la pile de (n+1) disques en (2C + 1) coups.
Attention ! Est-ce bien le nombre minimum de coups ou est-ce qu'on aurait pu mieux faire ? Réfléchissez un peu. Il va falloir à un moment ou un autre déplacer le disque du bas. Que faut-il faire auparavant ? Combien de coups cela prend au minimum ? Que faut-il faire une fois le disque du bas déplacé ? Combien de coups cela prend au minimum ?
Finalement, on a vu que s'il faut au moins cn coups pour déplacer n disques, il en faut au moins cn+1 = 2cn + 1 pour (n + 1) disques. Ce n'est pas mal, mais on voulait une formule en fonction de n.
D'après vos premiers essais, vous avez probablement conjecturé que cn = f(n) où f(n) est une fonction de n que vous avez déterminée. Si vous n'aviez pas assez de chiffres pour faire une conjecture, vous pouvez maintenant en avoir plus. Par exemple, pour 5 disques, il faut au moins 2x15 + 1 = 31 = 25 - 1.
Il semble que f(n)=2n-1 convienne. Comment vérifier que cette conjecture est vraie ? Essayez par induction.
- Il faut d'abord montrer que c'est vrai pour n = 1. A-t-on c1 = f(1) ?
- Maintenant, il faut montrer que si c'est vrai pour n = k, c'est aussi vrai pour n = k+1, i.e. que si ck = f(k), alors ck+1 = f(k+1).
Comme on a vu que ck+1 = 2ck + 1, il suffit de vérifier que f(k+1) = 2f(k)+1.
La prophétie va-t-elle se réaliser ?
Sachant que les moines ont n = 64 disques à déplacer, même en déplacant un disque par seconde, il leur faudra 264 - 1 secondes, i.e. au moins (264 - 1) / (60x60x24x366) > 238 années.
La prophétie a donc de grandes chances de se réaliser !!!
Indice :
Il fallait trouver 1, 3, 7 et 15. En ajoutant 1, on obtient donc 2 = 21, 4 = 22, 8 = 23 et 16 = 24.