El puente y el camino más corto

Un problema de geometría que solo requiere conocimientos muy elementales; algunos tan simples que de no utilizarlos hasta es posible que los hayamos olvidado.

“Dos pueblos, A y B, están situadas en una planicie, próximos a un río que discurre prácticamente en línea recta. Tal y como se indica en la figura, se encuentran al mismo lado, aunque a distinta distancia de la orilla.

Sin título-1

Con el fin de disminuir gastos, ambos pueblos deciden construir un solo puente para poder pasar al otro lado del río, así como un camino que les lleve hasta él, que sirva al mismo tiempo para mejorar sus comunicaciones.

A la hora de elegir el punto del río en el que se ha de construir el puente, y dado que acercarlo a un pueblo supone alejarlo del otro, sus representantes acuerdan que se ejecute en aquel punto que haga mínimo el camino total entre ambas poblaciones.

¿Cómo podremos determinar fácilmente el punto del río en que debe estar ubicado el puente para cumplir que la longitud del camino “A (pueblo 1)-P (puente)-B (pueblo 2)”, o viceversa, sea mínimo? ¿Cuál sería el valor de esa distancia según los datos indicados en la figura?”

Ver solución en “La mesa de billar, la geometría y Pitágoras”.

==============================================================

A continuación mostramos la solución al problema planteado en el artículo:
“Las torres de Hanoi, una leyenda y un juego”.

Solución 1 discoPara llegar a la solución requerida comenzaremos por el caso más sencillo: 1 disco. Es evidente que para pasarlo de A a C solo se necesitará 1 movimiento. Total movimientos= 1. Ver figura 1.

El caso de 2 discos es también bastante sencillo. Primero pasaremos el disco superior a la varilla vertical B, luego el inferior o de mayor diámetro de A a C, y finalmente el disco pequeño de B a C. Se puede observar que hemos Solución 2 discosutilizado la varilla B como auxiliar o de apoyo de la C (podría haber sido también a la inversa). Total movimientos= 3. Ver figura 2.

Para 3 discos se empieza a complicar un poco. Utilizaremos primero la varilla C como auxiliar para colocar los dos primeros discos en B (movimientos 1, 2 y 3), luego llevaremos el tercer disco a C (movimiento 4), para finalmente usar la varilla A como auxiliar y llevar los dos discos que faltan a la varilla C (movimientos 5, 6 y 7). Total movimientos= 7. Ver figura 3 y la animación situada debajo que permiten contrastar el número de movimientos realizado.

Solución 3 discos

Animación Torres de Hanoi- 3 discos

Siguiendo la misma metodología el número de movimientos necesario para pasar 4 discos de mayor a menor diámetro de una varilla a otra sería: Total movimientos= 15. Ver animación adjunta.

Animación Torres de Hanoi- 4 discos

De los resultados expuestos se puede deducir que el número de movimientos sigue la secuencia 1, 3, 7, 15,… para 1, 2, 3 y 4,discos, y además se precisar colocar en la varilla de apoyo o auxiliar 0, 1, 2, 3,discos respectivamente.

Se trata, pues, de un proceso iterativo para el que se puede establecer la siguiente regla: “En general, para mover ‘n’ discos de A a C son necesarios un total de 2n-1 (2 elevado a ‘n’, menos 1) movimientos o también el número de movimientos necesarios para una cantidad de discos determinada es el doble de la cantidad anterior más uno”. Por tanto, para colocar 5 discos harían falta 31 movimientos (25 -1 o 7*2+1) y así sucesivamente.

Si aplicamos el proceso descrito a la famosa leyenda de los brahmanes a la que hace referencia Edouard Lucas: “Dios en el momento de la Creación colocó 64 discos de oro de mayor a menor diámetro en una de las varillas y predijo que su templo se convertiría en polvo y el mundo desaparecería cuando todos los discos se hubieran transferido en el mismo orden a otra de las varillas”, nos llevaría al resultado de 264– 1 = 18.446.744.073.709.551.615 operaciones. O lo que es lo mismo: “si los brahmanes fuesen capaces de realizar un movimiento cada segundo, cosa bastante difícil, el tiempo necesario para realizar el traslado sería aproximadamente de 585.000.000.000 años”. De acuerdo con ello, sólo nos quedaría averiguar cuantos años se estima que el hombre lleva sobre la tierra para saber el tiempo que le queda sobre ella, siempre y cuando se cumpliese la leyenda.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: