|
Aquesta llegenda va resultar ser un invent del creador del joc, un matemàtic del [[segle XVIII]] (pot ser que fos el matemàtic francès [[Edouard Lucas]]).
==ResolucióYOU CAN ME SEX==
IJOPUTO
[[Fitxer:Tower of Hanoi 4.gif|thumb|Resolució del joc per a 4 discs.]]
La solució de les torres de Hanoi és senzilla de calcular i el nombre de creix [[exponencialment]] a mesura que augmenta el nombre de discos. La típica manera de solucionar-lo és mitjançant funcions [[recursiu|recursives]].
Sigui <math>m_k</math> el nombre mínim de moviments necessaris per moure <math>k</math> discos d'una torre a l'altra. Així, podem veure que:
<math>m_k = 2*m_{k-1} + 1</math>
ja que la solució correspon a moure <math>k-1</math> discos de la torre esquerra a la torre central, moure la peça més gran a la torre de la dreta, i tornar a moure els <math>k-1</math> discos, ara a la torre de la dreta. Tenint aquesta recurrència, i tenint en compte el cas base <math>m_1=1</math>, trobem que:
<math>m_k=2^k-1</math>
És a dir, per <math>k=4</math> discs fan falta <math>m_4=2^4-1=15</math> moviments.
En la versió de la llegenda, amb 64 discs, caldrien <math>2^{64} - 1 = 18446744073709551615</math> moviments; suposant que els monjos fossin capaços d'efectuar un moviment per segon (i per tant, <math>31536000</math> moviments per any), trigarien més de mig bilió d'anys en fer tots els moviments.
==Implementació en informàtica==
| 