TORRE DE HANOI
Este post es sobre un buenisimo juego matematico (para los que les gusta pensar un poco ) y sobre una solución utilizando como codificación para movimientos y posiciones el sistema binario.
LÓGICA
El juego esta formado por tres postes, en uno de ellos se encuentran apilados 'n' numero de anillos en orden de mayor a menor (de abajo hacia arriba), el objetivo del juego es pasar esa torre del poste en el que se encuentra inicialmente a uno de los otros dos postes, con las únicas restricciones de no poder mover mas de uno a la vez, y tampoco apilar un anillo de área mas grande sobre uno de área menor.
En la imagen se mira algunos movimientos del juego, y como termina la torre al final del juego.
HISTORIA
En el año de 1883, Édouard Lucas d'Amiens profesor francés publico este juego, aun siendo en Francia la publicación, el origen es de un lugar llamado (como el mismo titulo de juego lo dice) Hanoi, que esta situado al norte de Vietnam.
Que en su lugar de origen pues tiene una gran leyenda tras el, que también por eso se le llama "Las torres de Brahma" y "El problema del fin del mundo"
En el gran templo de Benarés, debajo de la cúpula que marca el centro del mundo, yace una base de bronce, en donde se encuentran acomodadas tres agujas de diamante, cada una del grueso del cuerpo de una abeja y de una altura de 50 cm aproximadamente. En una de estas agujas, Dios, en el momento de la Creación, colocó sesenta y cuatro discos de oro -el mayor sobre la base de bronce, y el resto de menor tamaño conforme se va ascendiendo-. Día y noche, incesantemente, los sacerdotes del templo se turnan en el trabajo de mover los discos de una aguja a otra de acuerdo con las leyes impuestas e inmutables de Brahma, que requieren que siemre haya algún sacerdote trabajando, que no muevan más de un disco a la vez y que deben colocar cada disco en alguna de las agujas de modo que no cubra a un disco de radio menor. Cuando los sesenta y cuatro discos hayan sido transferidos de la aguja en la que Dios los colocó, en el momento de la Creación, a otra aguja, el templo y los brahmanes se convertirán en polvo y, junto con ellos, el mundo desaparecerá
Análisis del juego
Llamaremos THn a un juego de la Torre de Hanoi de n discos. Llamaremos postes a las agujas de diamante o a los clavos en los que se insertan los discos. En el poste A, el de la izquierda, están insertados todos los discos al principio del juego y queremos mover la torre al poste C, el de la derecha. El poste B, el central, nos servirá de ayuda para depositar temporalmente algunos discos a lo largo del procedimiento. Llamaremos Mn al mínimo número de movimientos necesarios para solucionar THn. Consideraremos ordenados los discos de menor a mayor radio, de forma que el disco 1 es el más pequeño, el disco 2 el siguiente y, así, el disco n será el más grande y, por tanto, el que reposa en la base del juego.
Es claro que si n=1 entonces M(1)=1, pues basta desplazar el único disco del juego desde el poste A hasta el poste C. Si n=2, entonces hay que trasladar el primer disco hasta B, el segundo hasta C y, finalmente, el tercero hasta C. Por tanto, M(2)=3. Si n=3, entonces hay que trasladar los dos primeros discos hasta B, lo que requerirá M(2)=3 movimientos; luego el tercer disco hasta C y, finalmente, los dos discos pequeños desde B hasta C, lo que aporta otros M(2)=3 movimientos. Por tanto, M(3)=2M(2)+1=7. Como también M(2)=2M(1)+1, postulamos que, en general, se cumple que M(n)=2M(n-1)+1
La expresión anterior es una recurrencia. Busquemos ahora una fórmula explícita. Dado que M(1)=1=2^1-1, M(2)=3=2^2-1, M(3)=7=2^3-1, podemos postular que, en general, M(n)=2^n-1
Ahora recordemos un poquito de la historia, según la leyenda, eran 64 discos los que tenían que trasladar, por lo tanto el número mínimo de movimientos era:
M(64)=2^64-1=18 446 744 073 709 551 615
Los invito a estimar el tiempo de movimiento de cada disco y promediar el tiempo de vida de la tierra Lucas dijo que si los sacerdotes tardan un segundo en mover cada disco, estimaba que tardarían mas de 5 mil millones de siglos ( a mi me parece un poco exagerado, pero igual y no hice yo la prueba )
Una cosa importante que hay que mencionar es una regla que nos ayudara mucho y dice lo siguiente:
Nunca apiles dos discos pares o impares juntos
Ya dijimos que si enumeramos los discos de menor a mayor (lo cual dejaría al de menor área como 1 y al de mayor área como 'n') entonces, no debemos apilar consecutivamente el 5 con el 3 o el 7 con el 1 por ejemplo
bueno, creo que para la aplicacion binario es suficiente esto , bueno también lo que sigue para los que no saben mucho de el sistema binario por que, por lo menos como convertir de decimal a binario es necesario
SISTEMA BINARIO
Este sistema como su nombre lo dice binario esta constituido por solo dos símbolos; los cuales por convención se son el 0 y el 1; pero podrian ser otros, no importaria igual
Con el 0 y el 1 se forman cualquier numero que conocemos por el ejemplo el numero 4 es equivalente en binario al numero 100
un numero en binario no se lee igual que uno en decimal, por ejemplo si tenemos el numero 100; en decimal lo llamamos cien, en binario sería uno-cero-cero
Primero aclarar que en esa imagen la tercera columna no nos importa ahorita, es el sistema hexadecimal y pues para la torre de Hanoi no nos servirá, pero la imagen si me va a ayudar para explicarles un poco el sistema binario.
La primera columna es el sistema decimal, con el que mas trabajamos, la segunda columna es del sistema binario ahi podemos ver los primeros 15 números de cada sistema.
La lógica en el sistema binario es igual al decimal, que tanto conocemos primero colocamos todos los caracteres que conforman el sistema numérico de acuerdo a su orden (lo haremos primero con el decimal y luego con los binarios)
agregaremos unos ceros a la izquierda porque ayudan a la explicación
0000
0001
0002
0003
...
0009
y ahora??? se nos acabaron los caracteres de nuestro sistema mmm... bueno, entonces uno de los ceros de la izquierda tiene que cambiar, y comenzemos de nuevo
0010
0011
0012
...
0019
0020
....
0099
y bueno siempre se sigue esa lógica
0100
y bueno, asi como ya lo dijimos en binario es igual
0000
0001
Y ya se nos acabaron los caracteres, recuerden que solo son el 0 y el 1; pero al igual que en decimal, cambiamos el cero y pues seguimos
0010
0011
0100
0101
...
1111
bueno, con eso podríamos entender ya la solución, pero igual voy a explicar como se transforma de decimal a binario y viceversa, por que igual y nos ayudara en ciertas ocasiones.
Decimal a binario.
Pasar de decimal a binario es sencillisimo, solo son una serie de divisiones entre 2
por ejemplo tenemos el 26 (veinte y seis en decimal)
26/2=13 su residuo es 0
13/2=6 su residuo es 1
6/2=3 su residuo es 0
3/2=1 su residuo es 1
1/2=0 su residuo es 1
ahora ordenamos los residuos del ultimo al primero, entonces
26 es equivalente a 11010
Binario a decimal.
Para pasar de binario a decimal es un poquito mas complicado, pero tampoco dificil (siempre se me olvidaba, y aun haciendo el post, tube que recordarme y leer un poquito ) solo enumeramos de derecha a izquierda los dígitos del numero binario.
por ejemplo el 11010
0=0
1=1
0=2
1=3
1=4
luego multiplicamos cada dígito por dos y cada resultado lo elevamos a la potencia que cada uno le corresponde de acuerdo a la enumeración que hicimos anteriormente, todos esos resultados se suman.
(1*2)^4+(1*2)^3+(0*2)^2+(1*2)^1+(0*2)^0
esa suma da como total 26, que es el numero decimal correspondiente.
Solución de la Torre de Hanoi aplicando números binarios
Bueno por fin llegamos a lo que en realidad queria dar a conocer en el post pero igual, y eran necesarios todos los anteriores temas para entender bien la solución.
Supongamos que tenemos un Torre de 5 discos, por lo tanto el mínimo numero de movimientos necesarios para concluir el juego es 31 (gracias a la formula que analizamos anteriormente).
Ahora que ya sabemos que haremos 31 movimientos nos disponemos a contar (en binario) hasta 31 (11111)
Si se necesita agregamos mas ceros a la izquierda para completar 5 caracteres en cada numero que representaran a cada disco, el orden sera el mas pequeño es el caracter mas a la derecha y el disco mas grande sera el caracter mas a la izquierda.
Cada numero simboliza un movimiento, y el disco a mover sera en la posición que se encuentre el primer 1 (de derecha a izquierda)
En la imagen anterior podemos citar algunos movimientos, por ejemplo el movimiento cero es el inicio del juego, ningún disco se mueve en ese movimiento; en el movimiento uno, se mueve el disco mas pequeño (el disco uno), en el movimiento 10 se mueve el disco 2, en el movimiento 19 se mueve el disco 1.
Con esa lógica podemos saber que disco vamos a mover, pero aun nos falta saber hacia donde lo vamos a mover, recuerden que un disco 'x' esta ubicado en uno de los tres postes, por lo tanto, si vamos a mover ese disco tenemos dos posibilidades de moverlo (ademas del poste en el que esta hay dos postes mas)
Ciertamente no estamos seguros de hacia que poste vamos a mover el disco, pero con el numero binario de un movimiento 'x' podemos saber en que posición se encuentra cada disco, y se hace de la siguiente forma.
para poder saber, imaginamos un sexto disco, aun mas grande que el quinto, por lo tanto esta en la base de toda la torre al inicio, ese sexto disco no se movera, ya que nuestra torre consta de 5 discos reales, y los que vamos a mover son esos 5 discos.
y se utilizara la siguiente regla:
El disco k se encuentra sobre el disco k+1 si y sólo si son iguales los dígitos k y k+1 del numero binario de su movimiento correspondiente
También vamos a usar aquella regla de los pares e impares que se menciono anteriormente, y para que no halla confusión vamos a llamar poste0 al poste donde inicialmente están los discos y 2 donde van a terminar y 1 al intermedio.
Pongamos como ejemplo el décimo noveno movimiento: 19=10011
llamemos a(x) al posición 'x' del numero binario.
Entonces, como a(5)=1, el disco grande ya se ha movido y está, por tanto, en el poste 2. Como a(4) es diferente a a(5), el 4º disco no se encuentra sobre el 5º en el poste 2; tampoco podría estar en el poste 0 sobre el "disco 6" por que son pares los dos, así que se encuentra en el poste 1. Como a(3)=a(4) entonces el tercer disco se encuentra sobre el disco 4º en el poste 1. Como a(2) es diferente a a(3), el 2º disco no se encuentra sobre el 3º en el poste 1; tampoco podría estar en el poste 0 sobre el "disco 6" por paridad(son pares), así que se encuentra en el poste 2. Como a1=a2 entonces el primer disco se encuentra sobre el 2º disco en el poste 2
Con esa lógica podes saber hacia que poste moverás el disco, y pues con todo eso solucionas el juego
Ahora ya podes irle a ayudar a los sacerdotes, y asi que el mundo se termine mas rápido
claro solo si vos querés
Bueno pues espero haberme explicado bien y comenten si les gusto