Dans la version classique, on raisonne par récurrence:
x(1) = 1 et x(n) = 2.x(n-1) + 1 donnent: x = 2^n – 1
Dans la variante proposée, je raisonne aussi par récurrence:
- pour 1 seul disque, je dois passer par les deux autres piquets: x(1) = 2,
- pour n disques, je suis obligé de déplacer les n-1 disques trois fois pour
  pouvoir déplacer le plus grand disque deux fois: x(n) = 3.x(n-1) + 2,
- ce qui donne: x = 3^n – 1
Pour n = 50, je trouve x = 7,18 x 10^23 environ.
Mais que valide la case-réponse ?
A moins que je me sois trompé dans mon raisonnement.

On trouve pour le problème initial 2^N-1, donc ici je dirais 3*(2^(N-1)-1)+2, ce qui fait 3*2^(N-1)-1.

Pour N=50, je trouve 1688849860263935, mais ce n'est pas validé par la case réponse.

Ah ben oui, ça ne va pas car le 2ème plateau le plus grand ne passe pas par le centre dans ce cas.

Donc je corrige et propose (pour N > 1) : 7*2^(N-2)-1

Mais apparemment, tu proposes 3*2^(N-1), c'est bien ça ?
Tu arrives à faire 12 coups pour N=3 ?

Ah, ben pas de bonne réponse...
Dans le cas initial, l'idée est la suivante : pour N disques, la stratégie est de déplacer les N-1 premiers disques sur le piquet du milieu, puis le dernier disque sur le dernier piquet et les N-1 premiers disques sur le dernier piquet ensuite.

Autrement dit, tous les disques sont passés par tous les piquets sauf le plus grand (ils sont tous sur le piquet de départ au début, puis sur celui de milieu quand on déplace le plus grand; et enfin sur le dernier piquet à la fin). Le plus grand ne passe jamais sur le piquet du milieu.

Si on considère maintenant la stratégie suivante (celle de titoufred) :
- je déplace les N-1 premiers disques sur le dernier piquet
- je déplace le dernier disque au milieu
- je déplace les N-1 premiers disques sur le premier piquet
- je déplace le dernier disque sur le dernier piquet
- et enfin je déplace les N-1 premiers disques sur le dernier piquet
Dans ce cas là, l'avant dernier disque ne passe jamais sur le piquet du milieu; comme l'a remarqué titoufred.

Reste la stratégie suivante
- je déplace les N-1 premiers disques sur le piquet du milieu
- je déplace le dernier disque sur le dernier piquet
- je déplace les N-1 premiers disques sur le premier piquet
- je déplace le dernier disque sur le piquet du milieu
- je déplace le dernier disque sur le dernier piquet
(un aller retour en fait)
- et enfin je déplace les N-1 premiers disques sur le dernier piquet

Les N-1 premiers disques sont tous sur le piquet initial au début, tous au milieu après la première étape et tous sur le dernier à la fin. Et le dernier disque est sur le piquet initial au début, au milieu au début de l'aller retour et sur le dernier piquet à la fin.

Déplacer N disques se fait en 2^N-1 coups.
Par conséquent, pour chaque étape il faut
- 2^(N-1)-1 coups
- puis 1 coup
- puis 2^(N-1)-1 coups
- puis 1 coup
- puis 1 coup
- puis 2^(N-1)-1 coups
Total: 3*2^(N-1)

Exemple pour N=3:

1  |  |  
2  |  |
3  |  |
---------

|  |  |  
2  |  |
3  |  1
---------

|  |  |  
|  |  |
3  2  1
---------

|  |  |  
|  1  |
3  2  |
---------

|  |  |  
|  1  |
|  2  3
---------

|  |  |  
|  |  1
|  2  3
---------

|  |  |  
|  |  1
2  |  3
---------

|  |  |
1  |  |  
2  |  3
---------

|  |  |
1  |  |  
2  3  |
---------

|  |  |
1  |  |  
2  |  3
---------

|  |  |
|  |  |  
2  1  3
---------

|  |  |
|  |  2  
|  1  3
---------

|  |  1  
|  |  2
|  |  3
---------

Je me suis laissé piéger aussi.

scarta a écrit:

Total: 2*2^(N-1)

Tu as sans doute voulu écrire:
Total: 3*2^(N-1)