25.2.18

Cómo resolver las Torres de Hanói

Cuaderno de bitácora: gracias a la guía de nuestro compañero matenavegante Pablo Viedma, un día pudimos visitar, en nuestro periplo mateoceánico, las Torres de Hanói.

Este juego fue inventado en el año 1883 por un matemático francés, Edouard Lucas. Se trata de un solitario que se compone de tres pivotes o estacas verticales insertadas en un tablero y una pila con un cierto número de discos de tamaños crecientes, normalmente siete u ocho.

Figura 1.

El juego consiste en trasladar la pila entera de discos de uno de los pivotes a cualquiera de los otros dos, pero teniendo en cuenta las reglas:

-Sólo se puede tomar un disco en cada movimiento.
-El disco tiene que estar en la posición superior de su pila.
-Al pasarlo a otro pivote no se puede colocar sobre otro disco más pequeño.

Edouard Lucas, para dar mayor interés y contexto al juego, se inventó la leyenda de que el juego se había creado en un templo de Benarés, en la India, hoy ya desaparecido. Según esa leyenda, allí se comenzó con una Torre de 64 discos apilados.

Es fácil calcular el número mínimo de movimientos necesarios para trasladar toda la torre de una varilla a otra: 2n − 1, siendo n el número de discos que hay en la torre.

Si por ejemplo tenemos una torre de 8 discos, como en la figura 1, el número mínimo de movimientos será de:

28 − 1 = 256 − 1 = 255 movimientos.

En el caso de la leyenda del templo de Benarés, para mover toda la torre de 64 discos de un pivote a otro, se necesitarían:
264 − 1 = 18.446.744.073.709.551.615 movimientos como mínimo, más de 18 trillones.

Con un sencillo cálculo se puede comprobar que si hiciéramos un movimiento por segundo harían falta 584.942.417.355 años para completar todo el traslado.

El número total de movimientos para 64 discos nos recuerda otra leyenda famosa en matemáticas, la del inventor del ajedrez. Se dice que cuando el inventor presentó el ajedrez a su rey, este le ofreció como premio cualquier cosa que pidiera. El inventor pidió un grano de trigo por la primera casilla del tablero de ajedrez, dos granos de trigo por la segunda casilla, cuatro por la tercera, ocho por la cuarta, y así sucesivamente, doblando la cantidad de granos en cada casilla hasta completar las 64 de todo el tablero. Si calculamos el número de granos de trigo que hay que reunir en total nos sale exactamente la misma cantidad que los movimientos de la torre de 64 discos:

264 - 1 = 18.446.744.073.709.551.615 granos de trigo. (Para más información, consultar la entrada Leyenda sobre el tablero de ajedrez)

Hay estudios matemáticos muy completos sobre las Torres de Hanói. Es realmente interesante conocer la relación que existe entre las posiciones de los discos y los números del sistema binario. Otra actividad muy interesante para los grumetes es investigar en qué movimiento se mueve cada disco, y obtener así diversas progresiones aritméticas. Quizás dediquemos entradas futuras a tratar estos dos aspectos.

Pero enfrentémonos al juego e intentemos resolverlo. Nos daremos cuenta de que si los discos son muy pocos, dos, tres, hasta cuatro, trasladar la torre es sencillo. Pero a partir de cinco, seis discos... la cosa se empieza a poner complicada, el número de movimientos crece rápidamente y es muy fácil perderse.

Para ello hay dos trucos, cualquiera de los dos ayudan por separado a resolver el puzle, y si los combinamos entonces no podemos perdernos.

-El primer truco consiste en pintar los discos en dos colores diferentes, alternados, por ejemplo blanco y negro. También debemos pintar las bases de los pivotes en colores alternados: los pivotes libres uno debe ser negro de base y el otro blanco, y el pivote de partida debe tener el color contrario al disco más grande. Cuando tengamos pintados los discos y las bases debemos añadir una nueva regla: cada disco que movamos debe colocarse sobre otro disco o base de color contrario, nunca del mismo color.

-El segundo truco consiste en fijarse en que  el disco más pequeño, el que inicialmente está en la cúspide de la torre, se mueve en el movimiento 1º, 3º, 5º, 7º, 9º, ... en todos los movimientos impares. Empezamos moviendo el disco pequeño, movemos otro disco, luego otra vez el pequeño, luego otro disco, luego el pequeño otra vez, luego otro disco, luego el pequeño, y así sucesivamente. De cada dos discos que movemos, uno es el pequeño.

Además, siempre debemos mover el disco pequeño en el mismo sentido. Entre los pivotes hay dos sentidos de movimiento: el que podemos llamar sentido positivo o de izquierda a derecha, 1→2→3→1, y el que podemos llamar sentido negativo o de derecha a izquierda, 3→2→1→3.

Vamos a emplear este segundo truco o procedimiento para resolver este solitario. Haremos el ejemplo de una torre con 4 discos.

Figura 2.

A continuación ponemos la secuencia completa de 24 − 1 = 15 movimientos:

movimiento 1º: a1 → 2
movimiento 2º: b1 → 3
movimiento 3º: a2 → 3
movimiento 4º: c1 → 2
movimiento 5º: a3 → 1
movimiento 6º: b3 → 2
movimiento 7º: a1 → 2
movimiento 8º: d1 → 3
movimiento 9º: a2 → 3
movimiento 10º: b2 → 1
movimiento 11º: a3 → 1
movimiento 12º: c2 → 3
movimiento 13º: a1 → 2
movimiento 14º: b1 → 3
movimiento 15º: a2 → 3

Veamos los movimientos en una secuencia de fotografías:

Figura 3.
 a1 → 2
Figura 4.
 b1 → 3
Figura 5.
a2 → 3
Figura 6.
c1 → 2
Figura 7.
a3 → 1


Figura 8.
b3 → 2
Figura 9.
a1 → 2
Figura 10.
d1 → 3
Figura 11.
a2 → 3
Figura 12.
b2 → 1
Figura 13.
a3 → 1
Figura 14.
c2 → 3
Figura 15.
a1 → 2
Figura 16.
b1 → 3
Figura 17.
a2 → 3 y final.

Obsérvese que:

-El disco más pequeño, el a, siempre se ha movido de izquierda a derecha y en los movimientos impares, es decir, cada 2 movimientos.
-El segundo disco, el b, se ha movido de derecha a izquierda; se movió en el 2º movimiento y luego cada 4 movimientos (en el 6º, el 10º y el 14º).
-El tercer disco, el c, se ha movido como el a, de izquierda a derecha, empezando en el 4º movimiento y luego cada 8 movimientos (en el 12º).
-El cuarto disco, el d, se ha movido como el b, de derecha a izquierda, empezando en el 8º movimiento y luego le tocaba moverse cada 16 movimientos, pero como en nuestro ejemplo no había más que 15 movimientos, este disco sólo se ha movido una vez.

Con este ejemplo creemos que el lector puede guiarse para resolver el pasatiempo cuando la torre tiene más discos, aunque conforme el número de discos aumenta, el número de movimientos aumenta exponencialmente, y es difícil no perder la atención y confundirse en cualquier momento.

22.2.18

[El Problema de la Semana] Dos obreros camino del trabajo

Veamos este nuevo problema:

Dos obreros, uno viejo y otro joven, viven en un mismo apartamento y trabajan en la misma fábrica. El joven va desde casa a la fábrica en 20 minutos; el viejo en 30 minutos.

¿En cuántos minutos alcanzará el joven al viejo, andando ambos a su paso normal, si éste sale de casa 5 minutos antes que el joven?

Para la solución no hay que caminar nada, sólo girar la rueda del ratón.

Aquí tenemos una vieja e impresionante foto de 1930. Está tomada durante la construcción del Empire State Building de Nueva York. En ella un obrero de edad madura aprieta unas tuercas mientras está sentado sobre el vacío. A la derecha se aprecia el famoso edificio Chrysler. Como el edificio Chrysler mide en total 318,9 metros y en la foto parece estar por debajo del horizonte, podemos aventurar que el obrero de la foto se encuentra trabajando a más de 320 metros de altura. El Empire State Building fue inaugurado el 1 de Mayo de 1931, y tiene una altura total de 443,2 metros. [Extraído de la wikipedia]

SOLUCIÓN:

Podemos llamar e al espacio que ambos recorren, y que es el mismo. Según esto, la velocidad (espacio/tiempo) a la que va cada uno es:

Velocidad del joven: v1 = e / 20
Velocidad del viejo: v2 = e / 30

Teniendo en cuenta que el espacio es igual a velocidad por tiempo, el tiempo que tarda el joven (t) en alcanzar al viejo (que lleva caminando t + 5 pues sale 5 minutos antes) cumple la siguiente ecuación:

t · e / 20 = (t + 5) · e / 30

Simplificamos e en la ecuación, multiplicamos en cruz para quitar denominadores, quitamos paréntesis, y nos queda:

30t = 20t + 100

Y de aquí:

10t = 100; luego t = 10 minutos.

Otra forma más sencilla de razonar este problema es decir: si el joven tarda 20 minutos en hacer el recorrido, tardará 10 minutos en hacer la mitad del recorrido, y si el viejo tarda 30 minutos en hacer el recorrido, tardará 15 minutos en hacer la mitad del recorrido. Si el viejo sale 5 minutos antes que el joven, cuando este lleve 10 minutos andando se encontrará a mitad de recorrido, justo donde está el viejo en ese momento, que lleva 15 minutos andando

Nota: Este problema ha sido adaptado del libro Matemáticas recreativas, de Yakob Perelman.

17.2.18

Sudoku de letras (19)

Regla de este Sudoku: llenar las casillas vacías de forma que en cada fila, en cada columna y en cada caja de 3×3 estén todas las letras del siguiente conjunto:

A  C  E  F  I  L  N  O  R

Una vez resuelto, en la fila central aparecerá una palabra: el nombre de una hermosa ciudad italiana.


13.2.18

El Solitario

Cuaderno de bitácora: hace ya varios años que un compañero matenavegante me explicó cómo se resolvía el juego llamado Solitario. Como en los camarotes de nuestro nuevo Barco Escuela hemos encontrado un ejemplar de este juego, no voy a perder la oportunidad de compartir la solución.

El Solitario es un puzle formado por 33 cuentas o bolitas, colocadas en una trama en forma de cruz, como se aprecia en la ilustración.

Figura 1. 

Para poder describir los movimientos, vamos a numerar las posiciones de las bolitas:

Figura 2.

El Solitario comienza quitando la bolita central, la número 17:

Figura 3.

A partir de este momento, los movimientos permitidos son los que consisten en tomar una bolita y trasladarla saltando por encima de otra bolita que esté junto a la primera en horizontal, vertical, izquierda o derecha, a la casilla vacía que haya inmediatamente detrás de esta segunda bolita, y la segunda bolita se retira del tablero.

El objetivo es conseguir, tras exactamente 31 movimientos, que sólo quede una bolita en todo el tablero.

En la figura 3, por ejemplo, las únicas bolitas que se pueden mover son las que están en las posiciones 5, 15, 19 ó 29. Si por ejemplo tomamos la bolita 5 y la trasladamos a la casilla 17, saltando por encima de la bolita 10, retiraríamos esta bolita y quedarían vacías las casillas 5 y 10.

Es muy difícil resolver el solitario sin más indicaciones que las que hemos dado. Lo habitual es que pasemos horas y horas dándole vueltas a las bolitas, y siempre nos queden al final varias bolas aisladas que ya no se pueden retirar del tablero. El Solitario tiene tantas combinaciones que puede llegar a ser exasperante.

A continuación vamos a describir los pasos necesarios para llegar a la solución. Aquél que quiera intentarlo por sí mismo, no debe seguir leyendo.

La estrategia general es: eliminar el centro de la formación, y luego ir eliminando los bloques rectangulares de los cuatro brazos de la cruz, en sentido circular. Veamos las secuencias concretas.

Comenzamos realizando tres movimientos, que nos van a dejar un hueco en el centro en forma de L. La llamaremos la primera L, o la L pequeña:

15 → 17
4 → 16
17 → 15

Figura 4.
Así queda la disposición en L pequeña, tras los tres primeros movimientos.

Seguimos con otros tres movimientos que nos dejarán un hueco en forma de L grande o segunda L:

28 → 16
25 → 23
16 → 28

Figura 5.
Después de los siguientes tres movimientos nos queda este hueco con forma de L grande.

Nos fijamos en que nos han quedado a la izquierda y abajo, dos rectángulos formados por seis bolitas cada uno. La siguiente secuencia de 12 movimientos tiene como objetivo eliminar estos dos rectángulos; aunque es una secuencia larga, no es difícil aprendérsela y encontrarle la lógica:

7 → 9
14 → 16
9 → 23
22 → 24 (¿se nos ha quedado una bolita aislada en 21?)
31 → 23
24 → 22 (regresamos a rescatarla)
21 → 23 (rescate conseguido, y el rectángulo de la izquierda ya está limpio)
32 → 24
23 → 25
26 → 24
33 → 25
24 → 26

Figura 6.
Tras 12 movimientos más, hemos dejado limpia la zona inferior izquierda.

Ahora viene una parte un poco difícil de recordar. Se trata de 6 movimientos con los que vamos a eliminar el rectángulo de seis bolitas del extremo de la derecha, dejando una formación en L invertida de 8 bolitas:

27 → 25
18 → 30 (parece que nos alejamos, pero no es así)
20 → 18
11 → 25 (vamos al rescate de la bolita alejada)
30 → 18 (completado el rescate)
13 → 11

Figura 7.
6 movimientos más y ya nos quedan sólo 8 bolitas formando otra L gruesa e invertida en la parte superior.

Ya hemos llegado a la secuencia final de 7 movimientos. El movimiento final nos permite elegir entre dejar la última bola al centro del tablero, o bien dejarla en medio del extremo superior:

10 → 12
3 → 11
18 → 6
(ahora la bolita en 1 va a saltar consecutivamente sobre dos bolitas, como en las damas)
1 → 3
3 → 11
12 → 10
(nos quedan dos bolas sólo, llega el movimiento final)
5 → 17
(también podemos hacer 10 → 2 y acabar en 2).

Figura 8.
El Solitario solucionado, con la última bola al centro.

En este artículo hemos tratado una de las soluciones del Solitario estándar. Existen otras secuencias distintas de movimientos que también llegan a la solución.

El Solitario también se llama Senku, Uno Solo o Peg Solitaire en inglés. En la página de la wikipedia se puede encontrar mucha información.

Hay Solitarios con diferentes formas y otros números de bolitas. También se pueden tomar grupos de bolitas y disponerlos en formaciones más simples de resolver. Estas formaciones más sencillas son un buen punto de partida para aprender a realizar el Solitario completo, además ayudan a comprender la lógica de las secuencias de movimientos.

Por último, quiero agradecer al compañero matenavegante Pablo Viedma, que me enseñó a resolver el Solitario y me ayudó a apreciar un pasatiempo al que hasta ese momento no había prestado demasiado interés.

10.2.18

Sudoku de letras (18)

Regla de este Sudoku: llenar las casillas vacías de forma que en cada fila, en cada columna y en cada caja de 3×3 estén todas las letras del siguiente conjunto:

A  C  E  H  I  O  P  S  T

Una vez resuelto, en la fila central aparecerá una palabra en plural: muchas personas las están pagando durante muuuchos años.


7.2.18

[El Problema de la Semana] Caminando por el ecuador

Aquí tenemos un nuevo (pequeño) desafío:

Si pudiéramos recorrer la Tierra siguiendo el ecuador, la coronilla de nuestra cabeza describiría una línea más larga que la planta de los pies. ¿Qué magnitud tendría la diferencia entre estas longitudes?

Ilustremos la entrada y después escribamos la solución.

Aprovechamos para recordar cómo se definió originalmente el metro en 1795: como la diezmillonésima parte de la distancia que separa el ecuador terrestre de los polos. Posteriormente se actualizó la definición de metro, primero en 1889, mediante un patrón de platino e iridio conservado en los sótanos de la Oficina de Pesos y Medidas de París, y luego en 1960, como 1650763,73 veces la longitud de onda en el vacío de la radiación naranja del átomo del criptón 86. La información y la imágen están tomadas de la wikipedia.

SOLUCIÓN:

Llamamos R a la longitud del radio terrestre. Podemos suponer que nuestros pies caminan a lo largo de una circunferencia (perfecta) de radio R. La distancia que tienen que recorrer nuestros pies se calcula mediante la fórmula de la longitud de una circunferencia:

L = 2πR

Llamamos a nuestra estatura personal. Nuestra coronilla también traza una circunferencia, pero de radio R+e. Usando la misma fórmula de la circunferencia, podemos calcular la longitud que recorre nuestra coronilla.

L' = 2π(R + e) = 2πR + e

Gráfico del problema.

Restando ambas longitudes:

L' − L = 2πR + − R = e

Si nos fijamos, nos puede parecer sorprendente que lo que mide el radio de la Tierra se simplifica en la resta y no influye en el resultado. La diferencia de magnitudes sólo depende de nuestra estatura: e; si por ejemplo medimos 1,70 metros de estatura, la diferencia entre ambas líneas sería aproximadamente de 2·3,14·1,70 ≅ 10,7 metros, es decir, habría entre 10 y 11 metros de diferencia entre lo que recorren nuestros pies y lo que recorre nuestra coronilla.

Concretamente, la solución 2πe es la longitud de una circunferencia de radio nuestra estatura.

Nota: Este problema ha sido adaptado del libro Matemáticas recreativas, de Yakob Perelman.

3.2.18

Sudoku de letras (17)

Regla de este Sudoku: llenar las casillas vacías de forma que en cada fila, en cada columna y en cada caja de 3×3 estén todas las letras del siguiente conjunto:

A  C  E  I  N  O  P  S  T

Una vez resuelto, en la fila central aparecerá una palabra en plural: es lo mismo que los exponentes.