Missatge: Suposo que tothom sap com funciona el joc de les Torres de Hanoi. Resumidament: cal traslladar una torre d'una posició a una altra movent les peces d'una en una, amb l'única regla que les peces només poden anar sobre una peça més gran, o sobre la base.   Aviam si sabeu dir-me quin mínim de moviments cal fer per resoldre una torre de 4 peces? I pels més espavilats, quin mínim de moviments cal fer per resoldre-la amb qualsevol nombre de peces?  P.S: Espero que en Ziol trigui més de 15 minuts, aquest cop.

Resposta: Si volem moure n peces a una posició, el que podem fer és moure recursivament n-1 peces a l'altra posició lliure, després more la de baix on toca, i després tornar a moure recursivament les n-1 peces a on toca. Per tant la recurrència és a_n = 2*a_{n-1} + 1, i deixo la resolució de la fórmula exacta com a exercici :P