Según una leyenda, los monjes del templo de una antigua ciudad de la India tienen que mover una torre de 64 discos sagrados de un sitio a otro. Pero los discos son frágiles asi que sólo uno de ellos puede moverse a la vez. Ningún disco puede colocarse encima de otro más pequeño. Y únicamente existe otro lugar en el templo (además del sitio original y el destino) lo suficientemente sagrado para que una torre de discos pueda ponerse ahí.
La leyenda dice además que antes de que los monjes realicen el último movimiento para completar la torre en su nuevo lugar, el templo se reducirá a cenizas y el mundo se acabará. Quizá esta leyenda tenga razón debido a la cantidad de movimientos necesarios para cambiar de lugar los 64 discos. El total de movimientos que se necesitan es 18.446.744.073.709.551.615, exactamente la misma cantidad de granos de trigo que pedía el inventor del ajedrez como recompensa por su fantástico juego. Por ejemplo, la India entera, sembrados todos sus campos y destruídas todas sus ciudades, no bastaría para producir durante un siglo la cantidad de granos calculada.
Pero regresando al acertijo de las Torres de Hanoi, éste fué inventado en 1833 por el matemático francés Edouard Lucas y de hecho es un ejercicio que se deja a todo aquel que esté en una carrera donde la computación sea una parte medular. En términos generales está resuelto y es uno de esos problemas que pueden atacarse de mejor manera usando recursión. Sin embargo, no falta aquel que decide revisar el problema de las torres y halla nuevas ideas.
Por ejemplo, se tiene un algoritmo óptimo para cuatro postes. La pregunta es si esto ¿podría generalizarse a n postes? Hay muchos algoritmos que resuelven el problema en el número menor de movimientos y todos son equivalentes. Se puede probar que para el problema de las torres de Hanoi, con tres postes y n discos, se puede resolver en 2n-1 movimientos. En 1909 un libro de acertijos incluía una versión del popular pasatiempo pero con cuatro postes y con el nombre “El Acertijo de Reve“. Este es el primero de los acertijos en una secuencia n,m con n discos y m postes. El acertijo estándar es n,3.
Claramente cualquier generalización del acertijo tiene solución porque siempre se puede ignorar los postes adicionales y tratar el problema como si fuese del orden n,3. Sin embargo, el algoritmo sólo se ha probado de forma óptima para n,3 y no para n,4 o n,m. Esto es, se puede resolver el problema n,m en 2n-1, pero ¿podría hacerse en menos pasos o bien, cuál es la cantidad mínima de movimientos que son requeridos? Si hay postes adicionales, es claro que el número de movimientos se podría reducir pero nadie aún sabe cuál es el algoritmo óptimo.
En 1941 el American Mathematical Monthly publicó dos algoritmos equivalentes, por Frame y Stewart, que resuelven el problema general n,m pero no se probó que la solución fuese óptima. El algoritmo Stewart/Frame es para n discos, m postes y T(n,m) como el mínimo número de movimientos para un problema n,m.
De hecho, para alguna k, 1<=k<m, transferir los k discos de hasta arriba a un solo poste otro que no sea el poste destino, toma T(k,m) movimientos. Sin ahora tocar el poste que contiene los k discos, transferir los n-k discos al poste destino usando solamente los postes restantes n-1 toma T(n-k,m-1) movimientos. Todo el proceso toma 2T(k,m) + T(n-k,m-1) movimientos.
Bijoy Rahman Arif, de la Universidad IBAIS dice que ha probado que el algoritmo de Frame es óptimo, pero solamente en el caso cuando m=4. Si esto es cierto, entonces tenemos una solución para las torres de Hanoi con cuatro postes que es ótima y moverá todos los discos en T(n,4) = min sobre k de { 2T(k,4) + T(n − k,3) }
¿Se podrá generalizar el resultsdo para T(n,m) para m>4?
Fuente: Artículo de Rahman (pdf)