La ciudad de Kaliningrado, antiguamente llamada Königsberg, es un bonito lugar situado en la desembocadura del río Pregolya, en la antigua Prusia Oriental. Este río atravesaba la ciudad, diviendo la zona en varias partes. Para no perder la comunicación, ésta estaba llena de un sistema de puentes conectores.En total, había siete grandes puentes en Kaliningrado: El puente del herrero, el puente conector, el puente verde, el puente del mercado, el puente de madera, el puente alto y, por último, el puente de la miel. Los ciudadanos se sentían muy orgullosos de esta gran red de comunicación, y entre ellos surgió un pequeño juego para entretenerse en los momentos de aburrimiento:
¿Se pueden atravesar todos los puentes pasando sólo una vez por cada puente?Pensadlo por vosotros mismos, la imagen que introduce el artículo es el mapa de la ciudad con sus respectivos puentes.
¿Halláis la respuesta?
.
.
.
.
.
.
.
.
.
.
Bien, seguramente habréis decidido que es algo imposible, es necesario cruzar algún puente más de una vez. A base de repetir y repetir acabamos dándonos cuenta de que es un problema irresoluble. Sin embargo, los matemáticos siempre son mucho más elegantes a la hora de expresarse y hacer sus demostraciones, el método de "repetir y repetir" era algo demasiado informal.
Por aquella época, estaba en la ciudad un eminente matemático trabajando en la Academia Prusiana de las Ciencias. Como no podía ser de otra forma, enseguida se interesó por este acertijo y se propuso dar una solución mucho más completa y demostrativa de porqué es imposible cruzar todos los puentes sólo una vez. Este personaje se llamaba Leonhard Euler, posiblemente el mayor matemático de la historia.
En primer lugar, Euler simplificó el mapa del territorio a simplemente unas cuantas líneas y puntos. Eliminó todo lo sobrante:
Como podemos ver, los distintos territorios en los que los puentes dividieron la ciudad se convirtieron en puntos, es decir, en "vértices"; y los puentes se convirtieron en líneas, lo que llamamos "aristas". También determina que hay un punto de "inicio" y un punto de "salida".
Euler consiguió, a partir de este sencilló esquema, encontrar la solución de una forma mucho más elegante que la que aplicamos en un principio: Para poder recorrer un sistema de este tipo, los vértices "intermedios" deben tener un número par de aristas. Es decir, deben tener una vía para entrar y una vía para salir. Sólo los puntos de inicio y salida pueden tener un número impar de aristas, porque, evidentemente, nunca "entramos" al punto de inicio y nunca "salimos" del punto de llegada.
Es algo muy sencillo, vamos a crear mentalmente un sistema en el que hay un territorio divido en dos partes por un puente. ¿Cómo lo resolvemos? Tenemos que salir una vez del punto de inicio (nº impar), entrar en un punto intermedio y salir de él (nº par) y acabar entrando en el punto de salida (nº impar).
¿Y dónde reside la genialidad de Euler? En que este método se aplica a cualquier problema de este tipo. Con calcular las aristas que tienen los puntos intermedios y extremos podemos saber a la primera si el problema es irresoluble o no. En el caso de los puentes de Königsberg, los vértices intermedios tienen un número impar de aristas, por lo que es absolutamente imposible realizar la hazaña del ejercicio planteado.
También cabe destacar un último punto respecto al número de aristas que contienen los vértices de salida y llegada en un recorrido que sí se pueda completar (es decir, todo lo contrario a los puentes de Königsberg). Teniendo en cuenta que los vórtices intermedios tienen un número par de aristas, los vórtices de inicio y salida pueden tener, según la situación, un número par o impar de aristas:- Si el punto de llegada y salida es el mismo, obligatoriamente debe tener un número par de aristas (uno para salir y otro para regresar). Esto se conoce como "ciclo euleriano".
- Si por el contrario el punto de salida y el de llegada son diferentes, deben tener obligatoriamente un número impar de aristas. Esto es lo que conocemos como "camino euleriano".
Estos estudios realizados por Euler fueron el detonante de la teoría de grafos, convirtiendo una simple discusión pueblerina en toda una disciplina científica.
NOTA: Esta entrada participa en el Carnaval de Matemáticas (VI edición), que en esta ocasión organiza el blog Sangakoo, una iniciativa para difundir las matemáticas en la blogosfera.
Fuentes
Problema de los puentes de Königsberg - Wikipedia
1ª imagen
2ª imagen
3ª imagen
¡Suscríbete al blog por RSS!
También, puedes por E-Mail
¡O incluso a los comentarios!
17 comentarios:
¡Si estará visto este tema que hasta una egoblogokaka como el menda-lerenda ha escrito sobre esto! XD
Jajaja, Eulez, resulta que la inspiración para hacer este artículo me vino después de ver tu nombre y recordar a Euler y sus famosos puentes. Lo tenía guardado hasta ahora, que lo he desenterrado con ocasión del carnaval ;)
A ver si vemos más artículos de ciencia en tu egoblogokaka, que seguro que sacarías unos artículos de lujo XDD
Que increible! No conocia para nada este problema matemático/pueblerino xD Pensar que si los habitantes de la ciudad no hubieran estado tan aburridos como para pensar en estas cosas (o si la ciudad no tuviera sus puentes) tal vez una rama entera de las matemáticas no hubiera existido jamás.
Pues todo un genio Euler. Yo me he quedado pensando un buen rato, cruzando puentes de un lado para el otro y nada... Muy curiosa esta entrada, además me ha permitido jugar.
Cendero!!!! Me has iluminado!!!!
Pasé incontables años de instituto intentando resolver un problema similar.
Era algo así:
Tres cuadrados en línea horizontal, otros tres, también en horizontal, justo debajo.
La tarea consistía en unir cada uno de los cuadrados de arriba con los tres cuadrados de abajo sin que las líneas se cruzasen nunca.
¿Quién se atreve a intentarlo?
1. Simplificación.
2. Modelo gráfico.
3. Modelo matemático, si es simple, mejor.
4. Problema resuelto.
5. Extrapolación.
Pues eso, un genio el gran Euler. Elegancia sin complejos.
Y genial tu explicación, Cendrero
@Paquetolius
Señor Paquetolius, podría por favor ser más específico. Digamos por ejemplo, con un enlace que nos lleve a una imagen de su reto.
Con todo respeto, siempre lo he dicho el tendero de la esquina de mi barrio es igualito al señor Euler ¡Es increíble ja ja ja! El número e=2,718 aproximadamente, conocido a veces como número de Euler o constante de Napier fue reconocido y utilizado por primera vez por el matemático escocés John Napier, quien introdujo el concepto de logaritmo en el cálculo matemático (Fuente: Wikipedia).
0 0 0
0 0 0
Algo así Yunni. Ahora la tarea es unir cada uno de los 0 de arriba con todos los de abajo mediante líneas. La dificultad estriba en que las líneas no se pueden cruzar.
@Paquetolius
Era un clásico de los "instis". La gracia era que te decían que SÍ tenía solución. Y te rompías la sesera probando...
Ya ves Dani... qué recuerdos!
Yo siempre me quedaba a una línea de conseguirlo, pero era imposible.
Me toca responderle aqui, porque no me salen los comentarios, señor Paquetolius.
¡Ja ja ja! Los colombianos tendemos a la trampa y como no ha sido más específico, señor Paquetolius, me ha dado mucho campo libre para hacerle trampa (sé que usted lo tomara por el lado amable). Yo puedo resolverlo:
-Primera solución: No nos limitemos a las dos dimensiones. Con la tercera dimensión hay espacio suficiente para unir estos cuadros mediante líneas sin que se crucen.
-Segunda solución: Unamos todos estos cuadros mediante líneas, normal. Si alguien nos dice: “Pero las líneas se están tocando”. Les respondemos: “No se están tocando, porque nada toca nada”.” Nos sentimos mucho más cómodos con la idea de cosas que se tocan y se mueven, se estiran o se empujan, que con «campos» que mueven mágicamente objetos a distancia o meras abstracciones matemáticas. Pero, como señaló Feynman, nuestra sensación de que al menos en la vida cotidiana podemos confiar en el contacto físico sólido y sensible —para explicar, por ejemplo, por qué el cuchillo de la mantequilla se acerca a uno cuando lo coge— es un concepto erróneo. ¿Qué quiere decir tener contacto físico? ¿Qué ocurre exactamente cuando uno toma un cuchillo, o empuja un columpio, o hace una onda en el agua golpeando periódicamente sobre ella? Cuando investigamos en profundidad, encontramos que no hay contacto físico. En cambio, las cargas eléctricas de la mano están influyendo en las cargas eléctricas del cuchillo, columpio o agua, y viceversa. A pesar de la experiencia y el sentido común cotidiano, incluso aquí, sólo existe la interacción de campos eléctricos”. Página 377:
http://pycconsultores.net/images/CarlSagan-El%20mundo%20y%20sus%20demonios.pdf
Perdón por tardar tanto en responder, he estado un poquillo ocupado.
@Alfonso: Gracias, me alegro mucho de que te gustara :D
En mi opinión, aunque este suceso no hubiera ocurrido, me parece que sí que se habría descubierto la teoría de grafos, de alguna u otra forma. La ciencia se va descubriendo poco a poco, si no lo hace uno lo hará el siguiente científico. Por suerte, Euler tuvo esta gran genialidad y le mostró al mundo el camino a seguir para desarrollar esta teoría.
@Marcos Callau: Gracias! Lo mejor es que hayas podido disfrutar jugando un rato con los puentes, era una de las intenciones del artículo. De hecho, como avance de lo que se verá próximamente en el blog, te diré que estoy preparando una serie en la que podréis reflexionar y jugar mentalmente ;) Ya verás...
@Paquetolius: Jaja, genial que te haya ayudado este artículo, ya lo sabes para la próxima vez que te planteen un juego así :D
Bueno, pues un aspecto positivo de que haya tardado tanto en responder es que los demás han podido contestar ya a tu problema, ya te han dicho todo lo que tenía pensado contestarte ;)
@Dani: Y, también, genial tu resumen del método usado :) Euler fue un gran genio. No fue uno de los personajes más populares de la historia de la ciencia, una injusticia total. Yo siempre lo cito como uno de los mejores matemáticos que ha dado la historia, se merece mucho más reconocimiento del que se le da a veces en ambientes poco científicos.
@Yunni: Interesante el dato que comentar Yunni, gracias por aportarlo al artículo. Estaría bien conocer a tu tendero, no conozco a nadie que se parezca a Euler, la verdad, jaja. Gracias por pasarte por aquí.
@Paquetolius: Me has tenido un rato entretenido, no lo conocía ni lo había oído nunca :)
@Dani, @Pablo : Me estáis dando ideas para que se lo proponga a algunos cuantos que conozco, a ver si por lo menos ponemos a funcionar las neuronas un poco ;)
@Yunni: Yunni, menuda explicación, geniales tus trampas :D Eso es tener ingenio, así se puede resolver cualquier problema de este tipo, aplicando los "vacíos legales" del problema ;) Me ha gustado especialmente lo de usar las 3 dimensiones, muy útil.
@Cendrero (Adm. El Busto de Palas)
Yunni nos ha dejado a todos muertos con la tercera dimensión. Claro, si lee a Sagan es que es muy inteligente. :-)
Yunni, lo de la tercera dimensión ha sido lo más. jaja.
He estado ahí un rato a ver si podía solucionar el problema de los puentes :).
Mira que en el instituto me ponían cosas como estas diciéndome que tenían solución y al final nada... parece que nunca escarmiento xD.
Saludoss.
@Dani y @Paquetolius: Vaya, la tercera dimensión ha sido todo un puntazo ;) Nunca se me había ocurrido nada similar...
@Alive: Lo bueno de Euler y sus matemáticas es que él se ahorraba el paso de "probar y probar" para ver si podía ser cierto y saltaba directamente a la comprobación exacta mediante las matemáticas. Jeje, me alegro de que lo hayas probado antes de seguir leyendo, era uno de los objetivos del artículo ;-)
Gracias por pasar y saludos!
Felicitaciones por la entrada, Cendrero. No recordaba que la teoría de grafos fuera una materia tan entretenida, jeje... Muy bien explicado y muy ameno el contenido de esta publicación. Enhorabuena.
Un saludo.
Publicar un comentario