Réponses

2014-01-20T14:33:04+01:00
1a) Il faut 15 manipulations pour déplacer une tour de 4 étages
1b) Il faut 31 manipulations pour une tour de 5 étages
1c) On peut conjecturer que pour une tour de n étages, il faut 2^n-1 manipulations.
2) En effet, une tour de n étages est une tour de n-1 étages posée sur un disque.
Il faut donc 2^(n-1)-1 manipulations pour déplacer la tour de n-1 étages + 1 manipulation pour déplacer le dernier disque puis à nouveau 2^(n-1)-1 manipulations pour déplacer la tour de n-1 étages. Ca fait donc 2 x (2^(n-1)-1)+1= 2^n-2+1=2^n-1
En formalisant la démonstration par récurrence. a1=1=2^1-1=1 c Ca marche pour n=1.
Supposons que au rang n, an=2^n-1. Pour une tour de n+1 étage il faut déplacer la tour de n étage soit 2^n-1 déplacement puis déplacer le n+1 ème disque puis déplacer à nouveau la tour de n étages soit 2^n-1+1+2^n-1 déplacement soit 2^(n+1)-1 manipulations. Donc an+1=2^(n+1)-1
Peux-tu me dire quelle explication je peux mettre pour la 1a et 1b ^^
Sinon Merci Beaucoup déjà !