La torre de Hanoi

Aquest és un joc famós:

 

Es tracta de traslladar els tres discs de grandària decreixent de l’estaca A a la B, un disc cada vegada, però de tal manera que en cap moment un disc de grandària superior estigui a sobre d’un de grandària inferior.

La solució d’aquest cas senzill és : A passa a B, A passa a C, B passa a C, A passa a B, C passa a A, C passa a B i A passa a B.

Si en comptes de tres discs en tenim n, es pot comprovar  que existeix un algoritme per a solucionar-lo i que el nombre  mínim de passos és 2 (exponent n) – 1.  Aquest és, per tant, un exemple d’un problema que en la teoria de computació s’anomena exponencial i els problemes exponencials són per naturalesa difícils comparats amb els problemes que es poden resoldre en temps polinómic. El joc  va ser introduït a Occident pel matemàtic francès Édouard Lucas en el 1883.  Hi ha una història, no se sap si inventada per Lucas, de que hi havia un temple a la Índia amb tres estaques que contenien 64 disc daurats que els sacerdots  anaven movent i que el món s’acabaria el dia que completessin aquest trencacaps. Fent un moviment cada segon tardaríem 585 mil milions d’anys en resoldre’l, 127 vegades l’edat del Sol.