Per spostare n dischi devi prima togliere di mezzo gli n − 1 superiori, poi spostare una volta il disco più grande, poi rimettere quegli n − 1 sopra di esso. Quindi M(n) = 2M(n − 1) + 1 con M(1) = 1, che si risolve in 2ⁿ − 1: otto dischi richiedono 255 mosse e tre ne richiedono 7, sui primi due link. 255 risulterà familiare a chiunque legga le dimensioni della memoria — è il valore più grande che un byte senza segno contiene, esattamente per questo motivo.
La versione di Lucas veniva con sessantaquattro dischi d'oro e una profezia che il mondo sarebbe finito quando la pila fosse stata spostata. A una mossa al secondo sono 2⁶⁴ − 1 = 1.844674407371⋅10+19 mosse (terzo link), circa 585 miliardi di anni, più di quaranta volte l'età dell'universo — e il rompicapo a otto dischi davanti a te richiede un minuto e mezzo. Lo stesso raddoppio che rende banale il caso piccolo rende geologico quello grande, che è tutto il senso di un esponenziale: 255 e 1.844674407371⋅10+19 sono la stessa regola a sessanta differenze di distanza.
Risposta
255
Come leggerla
2⁸ − 1 sul banco di lavoro. Il secondo link è tre dischi; il terzo è il conteggio dei sessantaquattro dischi che fa finire il mondo.
Fonte
Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1
Svolgilo nella calcolatrice
Questi link aprono la calcolatrice giusta con i numeri di questo problema già digitati. La riga sopra è ciò che lo schermo dovrebbe mostrare — verifica tu stesso.