BLOG DE TECNOLOGÍA

"La duda es la madre del descubrimiento" Ambrose Bierce.

Posts Tagged ‘pasatiempo’

Torres de Hanoi

Posted by Administrador en enero 11, 2011

Os proponemos un juego interesante que, además, crearemos nosotros íntegramente, se trata de las Torres de Hanoi.

Las Torres de Hanói, o Torres de Diamante, es un famoso rompecabezas que inventó Éduard Lucas en 1883. Su origen está vinculado a una leyenda india que cuenta como en el gran Templo de Benarés, bajo la cúpula que señala al centro del Mundo, reposa una bandeja de cobre sobre la que se erigen tres agujas de diámetro más fino que el aguijón de una abeja. En el momento de la creación, Brahma colocó en una de dichas agujas 64 discos de oro puro ordenados de mayor a menor. Incansablemente, día tras día, los sacerdotes del templo mueven los discos haciéndolos pasar de una aguja a otra de acuerdo con las leyes fijas e inmutables de Brahma, que dictan que el sacerdote en ejercicio no mueva más de un disco al día, ni lo sitúe encima de un disco de menor tamaño. El día en que los 64 discos hayan sido trasladados desde la primera aguja a cualquiera de las otras dos la Torre, el templo y, con gran estruendo, el Mundo desaparecerán.

Basándose en dicha leyenda, Éduard Lucas, creó un juego similar al que llamó las Torres de Hanoi. El juego está formado por tres varillas verticales y un número indeterminado de discos (que determinarán la complejidad del juego, a más discos mayor será la dificultad). Los discos, de diferente tamaño cada uno, se colocan de mayor tamaño (el de más abajo) o menor (el de más arriba) en la primera varilla. El juego consiste en pasar todos los discos a la tercera varilla, en el mismo orden decreciente y respetando tres reglas básicas:

1ª. Sólo se puede mover un disco en cada tirada (aunque no cada día como hacen los monjes).

2ª. Nunca podemos depositar un disco de mayor tamaño que su inmediatamente inferior, es decir, nunca puede haber un disco de menor diámetro bajo otro mayor.

3ª. Sólo se puede desplazar el disco que se encuentre en la parte superior de la varilla.

Este juego es un conocido problema matemático muy utilizado en iniciación a la teoría de algoritmos. Para calcular cuantos movimientos necesitamos para su resolución simplemente debemos aplicar la siguiente fórmula, 2n-1, siendo n el número de piezas utilizadas en nuestro caso.

Así nos encontraremos que el número mínimo de movimientos para resolver el acertijo es:

– Si usamos 2 piezas → 3 movimientos.

– Si usamos 3 piezas → 7 movimientos.

– Si usamos 4 piezas → 15 movimientos.

– Si usamos las 64 piezas de la leyenda → 264-1, es decir, 18.446.744.073.709.551.615 movimientos. A movimiento por día… me temo que ninguno veremos el fin del mundo. Si suponemos un movimiento al segundo, los 64 discos estarían en la tercera varilla en unos 585 mil millones de años (si la Tierra tiene unos 5 mil millones de años…).

Como vemos el número de movimientos crece exponencialmente según aumentamos el número de fichas. Es por eso que debes empezar con pocas e ir aumentando la dificultad según vayas logrando superar el reto.

 

La construcción del juego la realizaremos próximamente en el taller. Trabajaremos con madera siendo el resultado final algo similar a esto:

Existe una opción más simple de jugar con las Torres de Hanoi. Consiste en realizar tres cuadrados sobre una hoja. Cada cuadrado corresponderá a una varilla. Por otro lado crearemos cuadrados de cartón (o cualquier material que sea grueso para poder cogerlo con facilidad). Mi consejo es que pintéis dichos cuadrados para que os resulte más fácil asimilar las diferencias de tamaño, y que sus áreas sean suficientemente distintas para facilitar el desarrollo del juego. Por supuesto el número de cuadrados dependerá de la dificultad que le queráis dar a la partida. Una vez realizados estos pasos previos. Créais una torre con todos los cuadrados ordenados de mayor a menor sobre el primer cuadrado de la hoja de papel y listos para jugar.

Aplicación para jugar online gratis a las Torres de Hanoi encontrada en la web http://www.uterra.com por Elena. Pincha en la imagen:

En el siguiente video podéis ver una aplicación realizada en Phyton que permite solucionar y practicar el problema. Será una aplicación que veremos más adelante en programación básica en la asignatura de Informática.

En el siguiente enlace se muestra el código en Phyton por si alguien quiere indagar un poco más. También podéis ver el código en C++, Prolog, Java o C# en el siguiente enlace.

Posted in Juegos, Programación, Taller | Etiquetado: , , , , , , , , , , , , , , , , | 2 Comments »

Topología, juegos y acertijos

Posted by Administrador en diciembre 8, 2010

La topología es una rama joven de las matemáticas que, principalmente se ocupa del estudio de las propiedades de los cuerpos geométricos que permanecen inalteradas por transformaciones continuas. Se trata de una disciplina compleja que no pretendemos abarcar de momento (interesante será ver más adelante el concepto de topología informática).

Nosotros nos vamos a quedar con la parte más sencilla, pero más entretenida de la topología. Son unos sencillos juegos matemáticos.

EJERCICIO Nº1.

Trata de formar la siguiente figura sin levantar en ningún momento el lápiz del papel ni pasar dos veces por la misma línea. Es difícil que salga al primer intento así que paciencia…

Ver video youtube con soluciones al ejercicio 1.

EJERCICIO Nº2.

El ejercicio de los 9 puntos. El juego consiste en pasar por los 9 puntos sin levantar el lápiz ni repetir línea. (Recuerda que en ocasiones nos autoimponemos normas que el problema no define). No es fácil aunque hay más de una solución. Si no te sale prueba a cambiar de estrategia hasta que lo consigas.

Ver video youtube con solución al ejercicio 2.

EJERCICIO Nº3. Los puentes de Königsberg. (dificultad muy alta)

Conocido también como el problema de los siete puentes de Königsberg. Se trata del problema que da origen a la topología. Su nombre procede de la antigua ciudad de Königsberg (actual Kaliningrado) en la Prusia del siglo XVIII. La ciudad estaba surcada por el río Pregolya, que, en el centro de la ciudad, se bifurcaba en dos brazos que rápidamente volvían a unirse formando en el interior una pequeña isla, llamada Kneiphof. El mapa de la ciudad quedaba de la siguiente manera:

El problema que se presentó era ¿es posible cruzar toda la ciudad a pie, pasando sólo una vez por cada uno de los puentes y regresando, finalmente, al punto de inicio? Puedes comenzar desde cualquiera de la regiones.

El enigma fue resuelto por Leonhard Euler (1736) que elaboró una teoría aplicable a casos similares.

Existe una simplificación que te puede ayudar a resolver el enigma. El mapa de la ciudad se puede reducir a una figura cómo ésta:

En la figura los puentes se representan con lineas y las zonas son los puntos de color azul. Así podríamos plantear el problema cómo ¿es posible dibujar dicho esquema sin levantar el lápiz ni pasar dos veces por una misma linea?

Solución en wikipedia.

Ver video con solución en youtube de los puentes de Königsberg (en inglés).

EJERCICIO Nº4. El caballo de ajedrez (dificultad media)

Se trata de un viejo problema que consiste en colocar el caballo de ajedrez en la posición de quieras del tablero (vale cualquier cuadrícula de 8×8) y, mediante el movimiento característico de dicha pieza (recorrer trayectorias en forma de L, es decir, se desplaza dos casillas en dirección horizontal o vertical y una casilla en la dirección perpendicular a la anterior) recorrer todas y cada una de las casillas de la cuadrícula sin repetir ninguna de ellas.

Existen múltiples soluciones, todas válidas, y muchos científicos (entre ellos el propio Euler) han buscado el algoritmo que resuelve el problema sin hallarlo. Existen diferentes técnicas que recomiendan seguir una trayectoria cíclica, recorrer continuamente el perímetro para luego abarcar el centro… inténtalo como tú quieras y se paciente  al resolverlo.

Mi consejo para realizarlo es: coge un trozo de papel. Haz una cuadrícula de 8 filas por 8 columanas (cómo el tablero de ajedrez) y vete probando fórmulas.

En la posición en que colocas el caballo pones un “1”, lo desplazas a la siguiente casilla y pones un “2” y así sucesivamente porque, recuerda que no puedes repetir casilla, por tanto, debes acordarte de por dónde pasaste. ¡Suerte!

Solución animada (una de las tantas válidas).

Solución fija (otra variante).

EJERCICIO Nº5. CRUCES (dificultad baja)

Se trata de, mediante una línea continua (no puedes levantar el lápiz), cruzar cada uno de los 16 segmentos que componen la figura sin pasar dos veces por ninguno de ellos. La figura es la siguiente:

Solución fija (video de youtube en inglés)

 

Posted in Juegos, Topología | Etiquetado: , , , , , , , , | 3 Comments »