miércoles, 6 de julio de 2011

LAS TORRES DE HANOI

Las Torres de Hanoi es un acertijo matemático que consiste de tres postes y varios discos de diferente diámetro con un orificio central, de manera que se puedan ensartar en los postes. Es un juego reglado, muy útil para adquirir la disciplina de jugar de acuerdo a unas reglas... y para otras ciencias en la resolución de problemas.

Estados y movidas

En el estado inicial del juego, todos los discos están en el poste 1 formando una pila, de tal manera que cada uno de ellos descansa sobre uno de mayor diámetro. En otras palabras, están en orden ascendente de tamaño, siendo el superior el de diámetro mínimo y el inferior el de diámetro máximo.
El estado final es esa misma pila en el poste 3 con los discos en el mismo orden del estado inicial.
Las movidas o jugadas legales para lograr ese estado meta o final están sujetas a las siguientes reglas:
  • Inicialmente se mueve el disco superior del poste 1 a cualquiera de los otros postes;
  • Cada una de las movidas posteriores consiste en trasladar el disco superior (de alguna de las pilas que se han formado) a otro poste;
  • Está prohibido colocar un disco sobre otro de menor diámetro. 
En resumen: Mover un disco a la vez y nunca colocar un disco sobre otro de menor tamaño.
Nota: Se suele agregar la restricción de que el estado final se logre con el mínimo número de movidas. Ver Torres de Hanoi (Wikipedia) para más detalles.
Sitios web interactivos de las Torres de Hanoi

Comentarios sobre la solución

El juego de las torres de hanoi es un ejemplo del método de resolución de problemas basado en casos particulares con números pequeños... Y después generalizar usando inducción.
Pero también es útil como ejemplo prototipo de problemas de estados y movidas: a partir un estado inicial, se quiere llegar a uno final, o estado meta, usando movidas legales (que se apegan a ciertas restricciones).
Para un disco se necesita una sola movida, para dos se necesitan 3, para tres... bueno para tres ya está más difícil... Pero podemos usar la solución  que ya sabemos para dos discos: traslado primero los dos superiores al poste intermedio (tres movidas), luego paso el disco inferior al poste 3 (una movida) y, finalmente, los dos del poste intermedio los paso al poste 3 (tres movidas). En total son 3+1+3=7.
De la misma manera puedo obtener el número de movidas para trasladar 4 discos al poste 3: 1) traslado los 3 superiores al poste intermedio (7 movidas), 2) paso el disco inferior al poste 3 (una movida) y, finalmente, paso los 3 discos del poste intermedio al poste 3 (7 movidas). En total son 7+1+7=15 movidas.
El procedimiento es fácilmente generalizable a n discos. Pero no solamente es generalizable para calcular el número de movidas, sino también para el procedimiento de trasladar los discos del poste uno al 3. Es decir, si lo sabes para dos lo sabes para 3, y si lo sabes para 3 lo sabes para 4, etc.

Solución para 2 discos

Inicialmente hay dos discos en el poste 1. Quiero pasarlos al poste 3 de acuerdo a las reglas. Entonces paso el disco pequeño del poste 1 al poste 2 (una movida), paso el disco grande del poste 1 al poste 3 y, finalmente, paso el disco pequeño del poste 2 al poste 3. Llamemos a este procedimiento P(2).

Solución para 3 discos

  • Aplico P(2) para pasar los dos discos superiores en el poste 1 al poste 2.
  • Paso el disco mayor del poste 1 al 3.
  • Aplico P(2) para pasar los dos discos en el poste 2 al poste 3.
    Llamemos a este procedimiento P(3).

Solución para 4 discos

  • Aplico P(3) para pasar los 3 discos superiores del poste 1 al poste 2.
  • Paso el disco grande del poste 1 al poste 3.
  • Aplico P(3) para pasar los 3 discos en el poste 2 al poste 3.
    Llamemos a este procedimiento P(4).
En general, si sabemos resolver las Torres de Hanoi para n discos, también lo sabemos resolver para n+1 discos. (A esta forma de razonar se le llama recursión. Ver el post sobre ese tema en MaTeTam - Matemáticas en Tamaulipas
Epílogo

Fácil ¿no es cierto? Pues no. Porque una cosa es al teoría ¡y vámonos a la práctica! Por propia experiencia sé que no es fácil resolverlo para más de 3 discos en el mínimo número de movidas, incluso sabiendo la teoría. Este es un ejemplo de que el significado está en el uso. ("Las reglas del juego parecen muertas. ¿Qué les da vida? En el uso están vivas.")
Ahora bien ¿cuál es el número mínimo de movidas? Llamemos a ese número T(n), para n discos. Sabemos que para n=1, 2, 3, 4,... se tiene que T(n)=1, 3, 7, 15,... ¿Cuál es el término n-ésimo?

Bueno, por lo que dijimos antes, debería ser claro que:



No es difícil conjeturar (a partir de los primeros términos 1, 3 ,7 ,15, ...) que el patrón es 

Veamos si cumple la recursión:


Y se ve que la conjetura es correcta: las Torres de Hanoi se pueden resolver en movidas, con discos.
Créditos: 

No hay comentarios:

Publicar un comentario

Tu opinión me importa, deja tu comentario...

1º BACH CCSS (32) 1º BACH CT (33) 1º ESO (40) 2º BACH CCSS (38) 2º BACH CT (34) 2º ESO (72) 3º ESO (52) 4º ESO (OPCIÓN A) (67) 4º ESO (OPCIÓN B) (56) 4º ESO DIV (39) ACERTIJOS (25) ACTIVIDADES (18) ACTIVIDADES RESUELTAS (30) AGUJEROS NEGROS NUMÉRICOS (1) ALGORITMOS (1) ALTURA (1) ANÁLISIS MATEMÁTICO (4) ANDROID (1) ANIMACIÓN A LA LECTURA (16) APPLETS (10) APROXIMACIONES (1) APUNTES (12) ARTE (1) AUDIOS (1) BASES (1) CÁLCULO (1) CALENDARIO (2) CALIFICACIONES (5) CARNAVAL (2) CITAS (12) COEDUCACIÓN (1) COMBINACIONES LINEALES (1) COMBINATORIA (1) CONSTANTE DE PROPORCIONALIDAD (1) CONTINUIDAD (1) CONTRACCIÓN (1) CONTRASTE DE HIPÓTESIS (2) CONVIVENCIA (1) CRÍTICA (3) CUADRADOS MÁGICOS (2) CURIOSIDADES (82) CURSOS DE FORMACIÓN (2) CURVAS (1) DEMOSTRACIONES (2) DEMOSTRACIONES INVÁLIDAS (2) DERIVADAS (3) DERIVADAS LATERALES (1) DESAFÍOS MATEMÁTICOS (27) DESPEDIDA (2) DILATACIÓN (1) DISTRIBUCIÓN NORMAL (1) DIVIDIR ENTRE CERO (1) DIVISIBILIDAD (1) DIVULGACIÓN CIENTÍFICA (4) DOMINIO (1) ECUACIONES (7) ECUACIONES DIFERENCIALES (1) EDUCACIÓN (4) EDUCACIÓN EN VALORES (9) ENTRETENIMIENTO (7) ERRORES (1) ESCALAS (1) ESPECTÁCULOS (1) ESTADÍSTICA UNIDIMENSIONAL (1) EXÁMENES (32) EXCURSIÓN (2) EXTREMOS (1) F. EXPONENCIAL (1) F. LOGARÍTMICA (1) F. POTENCIAL (1) F. PROPORCIONALIDAD INVERSA (1) FACTORIAL (1) FACTORIZACIÓN (2) FORMULARIOS (1) FOTOGRAFÍA (2) FRACCIÓN GENERATRIZ (4) FRACCIONES (2) FRACCIONES ALGEBRAICAS (1) FRATERNIDAD (1) FUNCIÓN A TROZOS (1) FUNCIONES (11) GEOGEBRA (9) GEOMETRÍA (4) GEOMETRÍA NO EUCLÍDEA (1) GRÁFICAS (2) GYMKANA MATEMÁTICA (2) HISTORIA DE LAS MATEMÁTICAS (2) HUELGA (1) HUMOR GRÁFICO (1) IGUALDAD DE GÉNERO (3) IMAGEN (1) INECUACIONES (1) INFERENCIA ESTADÍSTICA (2) INFINITO (2) INFORMÁTICA (3) INTEGRALES (1) INTERNET (1) INTERVALOS DE CONFIANZA (1) JUEGOS (5) KAPREKAR (1) LECTURA COMPRENSIVA (2) LECTURAS (7) LÍMITES (2) LÍNEA DEL TIEMPO (1) MAPAS TOPOGRÁFICOS (1) MATEMÁTICA RECREATIVA (36) MÁXIMO COMÚN DIVISOR (2) MÁXIMOS (1) MÍNIMO COMÚN MÚLTIPLO (2) MÍNIMOS (1) MUESTREO (2) MÚSICA (2) NOS MUDAMOS (1) NOTACIÓN CIENTÍFICA (1) NOVEDADES (125) NUEVO ALOJAMIENTO WEB (1) NÚMEROS CÓMPLICES (1) NÚMEROS COMPUESTOS (1) NÚMEROS DECIMALES (3) NÚMEROS ENTEROS (7) NÚMEROS IRRACIONALES (2) NÚMEROS NATURALES (1) NÚMEROS PRIMOS (3) NÚMEROS RACIONALES (2) OLIMPIADA MATEMÁTICA (3) OPERACIONES COMBINADAS (1) ORIGAMI (1) PAPIROFLEXIA (1) PARADOJAS (2) PAU (3) PENDIENTES (9) PERMUTACIONES (1) PERSONAJES (1) PI (1) PISA (2) PITÁGORAS (1) PODCAST (1) POESÍA (7) POLINOMIOS (2) PORCENTAJES (3) POTENCIAS (3) PRIMOS DE GERMAIN (1) PROBABILIDAD (1) PROGRESIONES (1) PROPORCIONALIDAD (4) PROYECTO LECTOR (4) PRUEBAS DE DIAGNÓSTICO (2) RADIO (1) RAÍCES (2) RAÍZ CUADRADA (1) RAZÓN DE PROPORCIONALIDAD (1) RECORRIDO (1) RECTA TANGENTE (1) RECURSOS (6) REDES SOCIALES (1) REFLEXIÓN (5) REGLA DE TRES (3) SELECTIVIDAD (3) SEXO (1) SISTEMA BINARIO (1) SISTEMA MAYA (1) SISTEMA SEXAGESIMAL (2) SISTEMAS DE ECUACIONES (3) SISTEMAS DE NUMERACIÓN (2) SUCESIONES (3) SUCESOS ALEATORIOS (1) TAREA EXPULSADOS (1) TENDENCIAS (2) TEOREMAS (2) TEORÍA DE GRAFOS (1) THATQUIZ (8) TORNEO MATEMÁTICO (4) TRASLACIÓN (1) TRIÁNGULOS (1) TRIGONOMETRÍA (2) TRUCOS (1) UNIDAD DIDÁCTICA (2) VARIACIONES (1) VECTORES (2) VIAJES (4) VíDEOS (14) VIOLENCIA DE GÉNERO (1) WALLWISHER (1) WEBQUEST (1)

Álgebra con papas (1) ANAYA Digital (1) Antonio Pérez Sanz (Blog) (1) Antonio Pérez Sanz (Web) (1) ASIPISA (1) Aula 21 (1) AVERROES (1) Aula TIC (1) BDMAT (1) Biografías Matemátic@s (Divulgamat) (1) Calculadora de funciones (1) Calendario Matemátic@s célebres (1) Calendario MatemáTICo (1) Carlos Ivorra (Web) (1) Citas célebres (1) Colegio Alcaste (1) Desafíos Matemáticos (El PAÍS) (1) DESCARTES (1) Disfruta las Matemáticas (1) DIVESTADÍSTICA (1) EducaPlay (1) ESTALMAT (1) Fotomat (1) Frases célebres Matemáticas (1) GeoGebreando (1) Glosario Matemático (1) Grupo Alquerque (Sevilla) (1) Historia de las Matemáticas (1) I.E.S. Arroyo de la Miel (1) I.E.S. de Pravia (1) Internet en el Aula (1) La Estadística en cómic (1) LIM (1) Láminas Matemáticas (1) Línea del tiempo (1) Mapa Matemático (1) Matematicaula (1) Matemáticas de cerca (1) Matemáticas en el Cine y TV (1) Matemáticas en Inglés (1) Matemáticas en la radio (1) Mathematical Moments (1) MaTeX (1) Música y Matemáticas (1) Olimpiadas Matemáticas (1) Origami (1) Papel para gráficas (1) Poesía Matemática (1) Poliedros (1) PROFES.NET (Editorial SM) (1) PROYECTO GAUSS (1) Paso de Mates (1) Rincón didáctico Matemáticas EducarEX (1) Sector Matemática (1) Selectividad.tv (1) Sellos Matemátic@s (1) SMconectados (1) TIC + TAC (1) Turismo Matemático (1) Wikimatemática (1) ZAI - Mates a tu alcance (1)



100 Problemas Matemáticos (1) Biblioteca Digital Mundial (1) Bibliotecas Digitales (1) Divulgación Matemática (Adrián Paenza) (1) El asesinato del profesor de Matemáticas (1) El diablo de los números (1) El hombre que calculaba (1) El hombre que calculaba (1) El Quijote (1) El Qujiote 1605-1905 (1) Historia y Filosofía de las Matemáticas (1) La Estadística en Cómic (1) La fórmula preferida del profesor (1) Las Matemáticas no dan más que problemas (1) LEA(h) Un libro donde reina el ingenio (1) Libros maravillosos (1) Literatura Matemática (1) Malditas Matemáticas (1) Matemática para todos (1) Matemática...¿Estás ahí? (1) Matemática...¿Estás ahí? Episodio 100 (1) Matemática...¿Estás ahí? Episodio 2 (1) Matemática...¿Estás ahí? Episodio 3,14 (1) Matemática...¿Estás ahí? La vuelta al mundo en 34 problemas y 8 historias (1) Planilandia (Una novela de muchas dimensiones) (1) Resolución de Problemas Matemáticos (Volumen I) (1) Resolución de Problemas Matemáticos (Volumen II) (1) Resolución de Problemas Matemáticos (Volumen III) (1) ¿Cómo, esto también es Matemática? (1)



Espejo Lúdico (1) Yair.es (1) Fotomat (1) Juegos y Matemáticas (1) Aula Pi MaTeMáTiCo (1) Aprender y enseñar Matemáticas (1) Algo más que números (1) Que no te aburran las M@tes (1) GeoGebreando (1) La Identidad de Euler (1) Mati, una profesora muy particular (1) MatemáTICas: 1,1,2,3,5,8,13,... (1) Matemáticas. Antonio Pérez Sanz (1) Matemáticas a nuestro lado (1) Apuntes matemáticos (1) ZAI - Mates a tu alcance (1) La Sabiduría del Co-razón. José María Toro (1)



Aprende a estudiar (1) Cuestionario Técnicas de Estudio (1) Técnicas de Estudio (1) ¿Cómo concentrarme? (1) ¿Cómo estudiar Mates? (1)



·