Problema ( Adaptación del problema original:" Las Torres de Hanoi " )

Se tienen tres torres, en una de ellas hay n anillos de diferentes tamaños, organizados por tamaño, de manera que el mayor esta debajo de los demás y así sucesivamente. El problema consiste en mover todos los anillos a otra torre, pero con la condición de mover solo uno cada vez, los anillos siempre tienen que estar en una de las torres y nunca se puede colocar un anillo mayor sobre uno menor.

Enumeremos los anillos como se muestra en la figura.

Donde 1 es el anillo mas pequeño y N es el anillo mas grande, es decir 1< 2< 3< ....... < N.

Sea : = 1=

Es decir: = 1=

.= , N, =

Los términos de la sucesión = { }, representan la secuencia de movidas (una a la vez), que se deben hacer para pasar los anillos de una torre a otra.

A continuación nombramos una serie de reglas que junto con la sucesión nos permitirá completar la solución del problema. Estas son:

1 - El anillo , avanza a la torre siguiente.

2- Si el anillo se encuentra en la ultima torre, entonces este avanza a la primera torre.

3- Si en la posición a la que avanzara el anillo , se encuentra el anillo y tal que > j, entonces el anillo sigue avanzando (bajo las condiciones anteriores 1 y 2).

Nota: 3 se da porque siempre se debe mantener 1 < 2 < 3......< N, y si un anillo mayor esta encima de uno mas pequeño se daría una contradicción, por ejemplo: 2<1 que es absurdo.

Veamos:

Por inducción matemática tenemos lo siguiente:

La situación se ilustra a continuación.

Situación inicial:

 luego por = 1 =, el anillo = 1 avanza a la torre siguiente , esto es:

Para N = 2, también se cumple , esto es para mover 2 anillos de una torre a otra la secuencia de movimientos es , veamos:

Situación inicial:

haciendo la secuencia se tiene:

1- El anillo 1 avanza a la torre siguiente:

2- El anillo 2 avanza a la torre siguiente, es decir a la torre 2 (pero como 2 > 1, entonces 2 sigue avanzando (regla 3)):

Ahora, supongamos que se cumple , es decir que N anillos pueden ser movidos a otra torre mediante la secuencia de movidas .

Ahora veamos que se cumple para k = N+1:

Supongamos que se tienen N+1 anillos:

Los primeros N anillos pueden ser movidos a otra torre siguiendo la secuencia (pues es cierto por hipótesis de inducción)

Luego de esto el anillo N+1 puede ser puesto en otra torre mediante un solo movimiento, así:

Luego los N anillos, pueden ser movidos nuevamente a la torre donde se encuentra el anillo N+1, mediante la secuencia de movidas , pues es cierto por hipótesis de inducción.

Es decir, para mover N+1 anillos de una torre a otra se hace lo siguiente : " Se mueven los primeros N anillos mediante la secuencia , se mueve el anillo N+1 a otra torre , se mueven nuevamente los N anillos a la torre donde se encuentra el anillo N+1 mediante la secuencia , pues es la secuencia para mover N anillos de una torre a otra".

Finalmente obtenemos que la secuencia para mover N+1 anillos de una torre a otra es: ,N+1, .

Pero ,N+1, =

Luego se cumple para k = N+1, Luego podemos concluir que se cumple y hemos concluido la prueba.

Para que nos quede mas claro veamos un ejemplo.

Se tienen tres torres, en una de ellas hay 3 anillos de diferentes tamaños, organizados por tamaño, de manera que el mayor esta debajo de los demás y así sucesivamente. El problema consiste en mover todos los anillos a otra torre, pero con la condición de mover solo uno cada vez, los anillos siempre tienen que estar una de las torres y nunca se puede colocar un anillo mayor sobre uno menor.

SOLUCION

Situación inicial:

Entonces hallemos :

Luego la secuencia de movidas es:

= 1 avanza a la siguiente torre (regla 1)

Estudiante Escuela de Sistemas

Universidad Nacional de Colombia - Sede Medellín