Los puentes de Konigsberg
¿Ven el mapa que hay ahí pintado? ¿Que es muy pequeño? Pues nada, una versión más grande si hacen clic en él. Eso que ven ahí es Konigsberg una ciudad de Prusia que ahora se llama Kaliningrado y está en Rusia. Como ven hay 7 puentes que unen las dos orillas del río y la isla. Ahora viene el acertijo: tienen que dar un paseo (imaginario) por Konigsberg de manera que pasen por todos los puentes una sola vez. ¿Sencillo, no? No hace falta ni siquiera que lleguen al mismo sitio, solo tienen que pasar por todos los puentes una sola vez.
La historia cuenta que este problema se lo estaban planteando los habitantes de la ciudad de los dichosos puentes y que nadie era capaz de encontrar el camino correcto, hasta que llamaron a Leonar Euler, el famoso matemático para que les resolviera el problema. Pues bien, Euler lo resolvió, vaya que si lo resolvió, encontró la solución general para este tipo de problemas que viene a ser la siguiente:
El problema tiene solución si de cada punto (en nuestro caso, cada porción de tierra) solo sale un número par de caminos (en nuestro caso, puentes) y además el punto de llegada será el mismo que el de salida.
Si hay dos puntos de los que sale un numero impar de caminos, también existe solución, pero llegaras a un punto distinto del de salida.
En cualquier otro caso, no hay solución.
¿Cual de estos tres es el caso de Konigsberg? Pues bien, según se ve en el dibujo, a la orilla norte (que sería uno de nuestros puntos) llegan 3 puentes (que equivaldrían a 3 caminos), a la isla llegan 5 puentes, a la orilla sur llegan 3 puentes y a la otra isla otros 3 puentes. Todos impares, asi que el problema no tiene solución.
Este problema es similar al que muchas veces se presenta en forma de "dibuja este dibujo sin pasar dos veces por la misma linea y sin levantar el lapiz del papel". Si alguna vez le plantean algo así, ya sabrá como resolverlo.
Y lo mejor de todo es que esto no es solo un acertijo más, los informáticos tienen estudian una cosa que son los grafos y que vienen a ser este tipo de esquemas, mientras que los matemáticos se dedican a la topología que tambiém tiene relación con este problema. Vamos, todo un dechado de virtud.
Etiquetas: Cosas de números
enviado por Sergio @ 8:13 p. m.
1 Comentarios:
Que vivan los grafos, los algoritmos de grafos, los problemas basados en grafos, la representación del conocimiento basada en grafos y el uso de grafos para simular el pensamiento humano y construir sistemas ingeligentes. Tu serebrro ess una máquina de Turring.
Publicar un comentario
<< Inicio