Torre de Hanoi
Torre de Hanoi
Torre de Hanoi
El juego, en su forma más tradicional, consiste en tres postes verticales. En uno de los postes
se apila un número indeterminado de discos perforados por su centro (elaborados de madera),
que determinará la complejidad de la solución. Por regla general se consideran siete discos.
Los discos se apilan sobre uno de los postes en tamaño decreciente de abajo a arriba. No hay
dos discos iguales, y todos ellos están apilados de mayor a menor radio -desde la base del
poste hacia arriba- en uno de los postes, quedando los otros dos postes vacíos. El juego
consiste en pasar todos los discos desde el poste ocupado (es decir, el que posee la torre) a
uno de los otros postes vacíos. Para realizar este objetivo, es necesario seguir tres simples
reglas:
1. Solo se puede mover un disco cada vez y para mover otro los demás tienen que estar
en postes.
2. Un disco de mayor tamaño no puede estar sobre uno más pequeño que él mismo.
3. Solo se puede desplazar el disco que se encuentre arriba en cada poste.
Existen diversas formas de llegar a la solución final, todas ellas siguiendo estrategias diversas.
Historia[editar]
El rompecabezas fue inventado por el matemático francés Édouard Lucas en 1883. Se cuenta
una historia sobre un templo en la India en Kashi Vishwanath que contiene una gran sala con
tres postes gastados por el tiempo, rodeada de 64 discos dorados. Los sacerdotes de Brahma,
actuando bajo el mandato de una antigua profecía, han estado moviendo estos discos de
acuerdo con las reglas inmutables de Brahma desde ese momento. Por lo tanto, el acertijo
también se conoce como el rompecabezas de la Torre de Brahma. Según la leyenda, cuando
se complete el último movimiento del rompecabezas, el mundo se terminará.2 No está claro si
Lucas inventó esta leyenda o si se inspiró en ella.
Si la leyenda fuera cierta, y si los sacerdotes pudieran mover los discos a una velocidad de
uno por segundo, utilizando el menor número de movimientos, completar la tarea les llevaría
264 - 1 segundos, o aproximadamente 585.000 millones de años,3 que es aproximadamente 42
veces la edad actual del Universo.
Existen muchas variaciones en esta leyenda. Por ejemplo, en algunos relatos el templo es
un monasterio, y los sacerdotes son monjes. Se puede decir que el templo o monasterio se
encuentra en diferentes partes del mundo, incluidos Hanói, Vietnam, y puede estar asociado
con cualquier religión. En algunas versiones, se introducen otros elementos, como el hecho de
que la torre fue creada en el comienzo del mundo, o que los sacerdotes o monjes solo pueden
hacer un movimiento por día.
Resolución[editar]
La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de
pasos para resolver el problema crece exponencialmente conforme aumenta el número de
discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver
un rompecabezas de la Torre de Hanoi es 2n - 1, donde n es la cantidad de discos.4
Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de
discos es impar la pieza inicial irá a destino y si es par a auxiliar.
Solución simple[editar]
Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba
en la varilla de origen. En un juego con un número par de discos, el movimiento inicial de la
varilla origen es hacia la varilla auxiliar. El disco 2.o n-1 se debe mover, por regla, a la
varilla destino. Luego, el disco n.o 1 se mueve también a la varilla destino para que quede
sobre el disco n.o 2. A continuación, se mueve el disco que sigue de la varilla origen, en este
caso el disco n.o 3, y se coloca en la varilla auxiliar. Finalmente, el disco n.o 1 regresa de la
varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Es decir, el truco está
en el disco más pequeño.
Mediante recursividad[editar]
Este problema se suele plantear a menudo en programación, especialmente para explicar
la recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila
de discos, destino a la tercera y auxiliar a la intermedia, y si a la función la
denomináramos hanoi, con origen, auxiliar y destino como parámetros, el algoritmo de la
función sería el siguiente:
1. sí origen entonces
1. mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila
destino)
2. terminar
2. si no
Iterativa[editar]
Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que
para obtener la solución más corta, es necesario mover el disco más pequeño en todos los
pasos impares, mientras que en los pasos pares solo existe un movimiento posible que no lo
incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles
se desplazará el disco pequeño. El algoritmo en cuestión depende del número de discos del
problema:
Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar
el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente
pila a su izquierda (o a la pila destino si está en la pila origen).
La secuencia será: destino, auxiliar, origen, destino, auxiliar, origen, etc.
HISTORIA
En el año de 1883, Édouard Lucas d'Amiens profesor francés, publicó este juego, aun
siendo en Francia la publicación, el origen es de un lugar llamado (como el mismo título
de juego lo dice) Hanói, que está situado al norte de Vietnam. Las Torres de Hanói
también son llamadas "Las torres de Brahma" o "El problema del fin del mundo".
La Torre de Hanói nos ofrece además, un amplio escenario para que ustedes evidencien
las competencias de su formación artística
Objetivo general:
El Cubo Soma es un rompecabezas de disección sólido inventado por Piet Hein en 1936
durante una conferencia sobre mecánica cuántica impartida por Werner Heisenberg. Siete
piezas hechas de cubos unitarios deben ser montadas en un cubo de 3x3x3. Las piezas
también pueden ser utilizados para hacer una variedad de otras figuras 3D.
Las piezas del Cubo Soma consisten en todas las posibles combinaciones de tres o cuatro
unidades de cubos, unidas por sus caras, de tal manera que se forme al menos una esquina
interior. Hay una combinación de tres cubos que satisface esta condición, y seis
combinaciones de cuatro cubos que satisfacen esta condición, de los cuales dos
son imágenes especulares entre sí (véase quiralidad). Por lo tanto, 3 + (6 x 4) es 27, que es
exactamente el número de celdas de un cubo de 3 x 3 x 3.
Este cubo ha sido analizado detalladamente por Martin Gardner y John Horton Conway, y el
libro Winning Ways for your Mathematical Plays (Vía a la victoria para tus juegos
matemáticos), contiene un análisis detallado del problema del Cubo Soma. Hay 240
soluciones distintas del rompecabezas del Cubo Soma, con exclusión de las rotaciones y
reflexiones: estas son fácilmente generadas por un sencillo programa de ordenador de
búsqueda recursiva de vuelta atrás similar al utilizado para el rompecabezas de ocho reinas.
Las siete piezas Soma son seis policubos de orden cuatro y uno de orden tres:
Pieza 1, o "V".
Pieza 2, o "L": una fila de tres bloques con un añadido por debajo del lado
izquierdo.
Pieza 3, o "T": una fila de tres bloques con un añadido por debajo del centro.
Pieza 4, o "Z": triominó doblado con el bloque colocado en el exterior del lateral a la
derecha.
Pieza 5, o "A": unidad de cubo colocada en la parte superior del lado de las agujas
del reloj. Quiral en 3D.
La resolución del Cubo Soma ha sido utilizada para una tarea para medir el rendimiento y el
esfuerzo de los individuos en una serie de experimentos de psicología. En estos
experimentos, se pide a los sujetos de prueba resolver un Cubo Soma tantas veces como sea
posible en un plazo determinado de tiempo. Por ejemplo, en 1969, Edward Deci, por aquel
entonces ayudante de cátedra de la Universidad Carnegie Mellon,2 le pidió a sus sujetos de
investigación resolver un Cubo Soma bajo condiciones de diferentes incentivos en su trabajo
de tesis sobre la motivación intrínseca y la extrínseca estableciendo la teoría social
psicológica de desplazamiento.
En cada una de las 240 soluciones al rompecabezas del cubo, solo hay un lugar en el que se
puede colocar la pieza "T". Cada cubo resuelto se puede girar de modo que la pieza "T" está
en la parte inferior con su borde largo a lo largo de la parte delantera y la "lengua" de la "T" en
el cubo central inferior (esta es la posición normalizada del cubo grande). Esto se puede
comprobar de la siguiente manera: si se tiene en cuenta que todas las posibles formas en que
se puede colocar la pieza "T" en el cubo grande (sin tener en cuenta ninguna de las otras
piezas), se verá que siempre va a llenar ya sea dos esquinas del gran cubo o cero esquinas.
No hay manera de orientar la pieza "T" de manera que llene solamente una esquina del cubo
grande. La pieza "L" puede estar orientada de manera que llene dos esquinas, o una esquina,
o cero esquinas. Ninguna de las otras cinco piezas tienen una orientación que llene dos
esquinas; que pueden llenar ya sea una de las esquinas o rincones cero. Por lo tanto, si se
excluye la pieza "T", el máximo número de esquinas que pueden ser ocupadas por las seis
piezas restantes es de siete (una esquina cada una para cinco piezas, además de dos
esquinas para la pieza "L"). Un cubo tiene ocho esquinas. Pero la pieza "T" no puede ser
orientada para llenar solo una de las esquinas restantes, y orientándola de manera que llene
cero esquinas lógicamente no forma un cubo. Por lo tanto, la "T" siempre debe llenar dos
esquinas, y solo hay una orientación (descontando las rotaciones y reflexiones) en las que
hace eso. También se deduce de esto que en todas las soluciones, cinco de las seis piezas
restantes rellenarán su número máximo de esquinas y una pieza rellenará uno menos que su
máximo (esto se llama la pieza deficiente).3
El CUBO SOMA es un rompecabezas tridimensional, diseñado en 1936 por el
poeta , soñador, matemático y escritor danés Piet Hein.
No fue demasiado popular hasta 1969 cuando Parker Bros lo empaquetó como
"La respuesta 3D al Tangram", pero tuvo la mala suerte de coincidir con otro cubo
de 27 piezas que se hizo mucho más popular y absorbió durante bastante tiempo
la atención de los puzzles de forma cúbica.
Está constituido por 7 piezas (6 de ellas formadas por 4 pequeños cubos y una
sólo por 3) que son todas las figuras cóncavas que podemos formar con 3 ó 4
cubos pequeños adosados por una cara. Las siete figuras o piezas del Soma se
pueden identificar con un número o con una letra:
Objetivos a conseguir:
Ally Capellino le encargó a Seng Watson la realización de una serie de “stands” para
colocar, durante el London Design Festival, sus bolsos y otros complementos en las
tiendas que Capellino tiene en Londres. Una de las inspiraciones del proyecto
“Polyomino” fue la arquitectura “brutalista” londinense de los años 1960, en la que
está también inspirada la colección otoño/invierno 2014 de Capellino. El arquitecto
decidió realizar los “stands” con las piezas del “cubo soma”, a partir de cubos de
27.250 mm3 de “papercrete” (hormigón de papel), una mezcla de cemento y papel,
que hace que las piezas del diseño tengan el aspecto crudo del hormigón, pero sean
a la vez ligeras y manejables.
Las siete piezas del proyecto
“Polyomino” realizadas en hormigón de papel
“Stands” del proyecto
“Polyomino” con bolsos y complementos en una de las tiendas de Ally Capellino en
Londres
Curiosamente, el nombre del proyecto, “Polyomino”, es confuso, puesto que las
piezas del “cubo soma” no son poliominós (es decir, figuras geométricas planas
formadas conectando dos o más cuadrados por alguno de sus lados), sino que son
policubos (esto es, figuras geométricas tridimensionales que se forman al unir dos
o más cubos por alguna de sus caras). Solo cuatro de las piezas del “cubo soma”
podrían ser consideradas poliominós, puesto que son las cuatro piezas “planas” del
puzzle, aquellas que pueden colocarse para que tengan solo la altura de un cubo, y
no más altura, como ocurre en las otras tres piezas (véanse las piezas del “cubo
soma” de la siguiente imagen).
Fue durante una conferencia sobre mecánica cuántica del premio Nobel de Física,
Werner Heisenberg (1901-1976), cuando Piet Hein se dio cuenta de que con todos
los policubos irregulares formados por 4, o menos, cubos (matemáticamente que
sean irregulares quiere decir que cada uno de esos policubos es no convexo, es
decir, que dados dos puntos cualesquiera del mismo no es cierto que todos los
puntos que están en el segmento que los une estén también en el policubo, por
tanto hay que descartar los regulares, que son o una serie de cubos alineados, uno,
dos o tres, o un “cuadrado” formado por cuatro cubos), que son siete, se podía
formar un cubo 3x3x3.
Las piezas del “cubo soma”
Las siete piezas del juego de ingenio que Piet Hein bautizó con el nombre de “cubo
soma” son un policubo formado por tres cubos (con la forma de una L “corta”) y
seis policubos formados por cuatro cubos (una esquina o trípode, una L “larga”,
una T, una Z y otras dos piezas que son una la imagen especular de la otra).
Este puzzle geométrico, que consiste en formar un cubo de tamaño 3x3x3 con los
siete policubos irregulares, admite 240 soluciones distintas. Y fueron los
matemáticos ingleses John H. Conway y Richard K. Guy quienes obtuvieron la lista
completa de las 240 soluciones, “en una tarde lluviosa de 1961”.
Para empezar, como vemos en la siguiente imagen, asocian cada pieza del puzzle a
un número y un color, para poder identificarlas.
Pero fijémonos en los vértices, que son 8, y veamos cuántos vértices pueden ser
ocupados, como máximo, por cada una de las piezas del “cubo soma”. La pieza
blanca solo puede ocupar 1 vértice, la pieza amarilla 2 vértices, la verde 2 vértices,
la naranja (en nuestro caso, multicolor) 1 vértice, y de la misma forma, las piezas
azul, roja y negra pueden ocupar solo 1 vértice.
Coloreemos ahora los 27 cubos del cubo 3x3x3 final con dos colores, blanco y
negro, y de forma alternada, es decir, si un cubo es blanco, los cubos que tocan a
este cara con cara, serán negros. Así, los cubos que son cara o vértice en el cubo
grande serán de color blanco, mientras que los cubos laterales y el central serán de
color negro, como aparece en la siguiente imagen.
Tomemos una solución cualquiera del “cubo soma”, por ejemplo, la que aparece en
la siguiente imagen, y computemos el número de cubos blancos y negros que ocupa
cada pieza del puzzle en esa solución.
Una solución del cubo soma
Vemos que en esa solución el número de cubos blancos y negros de cada pieza es el
siguiente:
Si nos fijamos en las piezas de color amarillo, naranja (en nuestro cubo, la pieza
multicolor), azul y rojo, estas van a tener siempre estos números, es decir,
ocuparán 2 cubos blancos y 2 negros. Puesto que la pieza de color verde no puede
ser deficiente, como hemos justificado anteriormente, entonces tiene que ocupar
dos vértices, lo que la obliga a que siempre ocupe 3 posiciones de cubos blancos y 1
de negro, como en la anterior solución. La pieza de color blanco podría ocupar 2
cubos blancos y 1 negro, o al revés, así como la pieza de color negro podría ocupar 1
cubo blanco y 3 negros, o al revés. Sin embargo, como la cantidad total de cubos
blancos (14) y negros (13) es siempre la misma, y las otras piezas no cambian la
cantidad de cubos blancos y negros, entonces las piezas de color blanco y negro
tampoco podrán cambiar, y los números que aparecen en la tabla anterior son
válidos para cualquier solución del “cubo soma”.
¡¡En cada solución del cubo soma, la pieza de color blanco ocupa 2 posiciones
blancas y 1 negra, y la pieza de color negro ocupa 3 posiciones negras y 1
blanca!!.
Estas restricciones que acabamos de describir son muy fuertes, puesto que nos
determinan que posiciones pueden ocupar, y cuales no, cada una de las siete piezas
del puzzle tridimensional.
Pero dejemos ya esta parte matemática del puzzle de Piet Hein, relacionada con la
combinatoria (el cálculo del número de soluciones del juego), y terminemos la
entrada con un par de ejemplos de la presencia del “cubo soma” en el arte.
4.- Pedro Alegría, Santiago Fernández, Raúl Ibáñez, Goyo Lekuona, Juegos
didácticos para el programa BBK-máticas, las matemáticas en las bibliotecas
escolares, Fundación BBK, 2009. [www.divulgamat.net]
5.- Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, Winning ways for your
mathematical plays, volume 4, A.K. Peters, 2004.
8.- Simon Dybbroe Møller , “Letter From the New World to theOld World”
Esta entrada participa en la XII Edición del Carnaval de Humanidades, cuyo blog
anfitrión es ::ZTFNews.