Los siete puentes de Königsberg

Seguro que cuando eras pequeñ@, en la escuela, alguna vez algun amig@ tuy@ te habrá pedido que resuelvas el problema de la casita. El problema es sencillo, tienes que pasar por todas las esquinas sin repetir ninguna y cubriendo todas las líneas. Al menos yo, como cuando me lo dijeron tenía 7 u 8 años pues lo que hice fue tirarme sin pensar a hacerlo y fallé unas cuantas veces, incluso creí que me habìan engañado y era imposible de resolver.

Pues aunque no te lo creas, un problema como el de la casita tuvo un gran impacto en las matemáticas actuales. Incluso el gran Euler dedicó una gran parte de su tiempo y sus investigaciones a explicar el fenómeno. Se trata de los los siete puentes de Königsberg.

→ →

Könisberg (actual Kaliningrado) era una ciudad de Prusia que tenía 7 puentes que cruzaban el río Pregel. El problema era el mismo que el de la casita, ¿puede una ruta atravesar todos los puentes una sola vez?

Euler demostró que la respuesta es NO y formuló una teoría que se puede aplicar a todos los problemas de este tipo como el de la casita. Lo primero que hizo fue convertir el problema de la ciudad real en el dibujo de la derecha, con ese dibujo se ve claro que hay cuatro puntos o nodos y 7 rayas o enlaces. El problema ha de ser resuelto en función del grado de los nodos, esto es, el número de enlaces que le llegan. El problema de los puentes tiene 3 nodos de grado 3 y 1 nodo de grado 5.

Para demostrar el teorema, Euler llamó a cada isla con una letra mayúscula y a cada puente con una letra minúscula

 

 

En primer lugar, si para ir de A a B hubiese dos puentes, no importa el puente que se coja, el resultado será el mismo. Además teniendo en cuenta que para ir de A a B se cruza un sólo puente (secuencia AB) y se necesitan dos letras, para ir de A a B y luego a C (ABC) se necesitan dos puentes y tres letras, etc. Se comprende que se necesita una secuencia de 8 letras para cruzar los siete puentes (7+1=8).

Además tenemos que sea la isla que sea, se dará una situación similar a esta (hacer click en la imagen):

 

En esta situación al atravesar “a” o bien llegamos o bien salimos de A, al atravesar los puentes “a”, “b” y “c” pasamos dos veces por A y así sucesivamente, es decir el número de veces que pasamos por A (N) al atravesar todos los puentes será el número de puentes (n) más 1 y dividido por 2:

N=(n+1)/2

De esta forma tenemos que en nuestro problema de los puentes (figura 1) como a A le llegan 5 puentes habrá que pasar 3 veces por él, y como B, C y D tienen 3 puentes habrá que pasar dos veces por cada uno de ellos, por tanto, 3 veces por A más 2 veces por B más 2 veces por C más 2 veces por D, son 9 letras, y como ya habíamos dicho antes se deberían necesitar sólo 8, por tanto ahí hay una contradicción.

A+A+A+B+B+C+C+D+D=9

Esta contradicción demuestra que NO se puede resolver el problema, no hay un camino de Euler que atraviese todos los puentes una vez cada uno.

Otro día explicaré por qué esta teoría se puede extender al problema de la casita.