Los puentes de Königsberg

Uno de los problemas más populares de todos los que resolvió Leonard Euler, fue el de los siete puentes de Königsberg. El asunto es el siguiente: por la ciudad de Königsberg (hoy Kaliningrado) pasa el río Pregel, al cual pertenecen dos islas que están comunicadas entre si y con las márgenes del río por siete puentes $a$, $b$, $c$, $d$, $e$, $f$ y $g$, como se ilustra en la figura 10.

Figura: Puentes de Königsberg

El problema consiste en determinar si es posible trazar un recorrido que pase por cada puente una y solo una vez. Euler logro demostrar en una memoria publicada en San Petersburgo en 1736, que esto no puede hacerse. El análisis que empleo sirvió para desarrollar una rama de la matemática, llamada Topología combinatoria. Vamos a presentar el método que siguió.

Denoto con las letras $A$, $B$, $C$ y $D$ las cuatro regiones en que queda dividida Königsberg por el río, como se indica en la figura 10. Si una persona va de la región $A$ a la $C$ independientemente si usa el puente $c$ o el $d$, notamos este paso por $AC$. Si después va de $C$ a $D$ notamos $CD$; para indicar que se han realizado ambos pasos notamos $ACD$.

De la misma forma la expresión $C A D B A D$, indica que la persona partió de $C$ hasta $A$, siguió de $A$ a $D$, luego de $D$ a $B$, después de $B$ a $A$ y por último de $A$ a $D$. Para hacer este recorrido tuvo que pasar por $5$ puentes. En general si el recorrido que siguió una persona esta indicado por $n$ de estas letras $(A, B, C y D)$, es porque tuvo que pasar por $n-1$ puentes.

$$A \to B a b$$

$$B \to D f$$

$$D \to C g$$

Estuvimos en cuatro sitios ($A$, $B$, $D$, $C$), y recorrimos tres puentes ($a$ o $b$, $f$, $g$).

Por lo tanto, el paso por los $7$ puentes de Königsberg, requiere de $8$ letras para designarlo.

Por otra parte, si a una región $E$ conducen $7$ puentes y una persona desea realizar un recorrido que incluya estos $7$ puentes de tal manera que pasa solo una vez por cada uno, entonces en la secuencia de letras que denota el camino recorrido aparecerá exactamente $4$ veces la letra $E$, por lo siguiente:

Supongamos que empezó el recorrido por fuera de $E$ y notemos $E^c$ la parte exterior de $E$.

Inicialmente hace el recorrido $E^cE$ pasando por el primer puente. Como tiene que salir, hace el recorrido $EE^c$ pasando por un segundo puente; de tal forma que aunque ha pasado por dos puentes, solo aparece una vez la letra $E$ (El recorrido completo en este caso es $E^c E E^c$)

Mas adelante tendrá que realizar el recorrido $E^cE$ pasando por un tercer puente y necesariamente hará $EE^2c$ pasando por un cuarto puente; aqui nuevamente ha agotado dos puentes pero ha agregado una sola letra $E$ a la secuencia que denota el trayecto.

Tarde o temprano tendrá que hacer $E^cE$ pasando por un quinto puente y lógicamente $EE^c$ pasando por un sexto puente. Nuevamente tenemos dos puentes y una sola letra $E$.

Finalmente tendrá que hacer $E^cE$, pasando por el último puente y agregando una $E$ a la secuencia.

En la figura 11 están numeradas las veces que estamos en $E$. Nótese que si en lugar de partir de $E^c$, partimos de $E$ el resultado es el mismo. Vemos que el número de veces que aparece la letra $E$ es $4$.

Figura: Puentes de Königsberg (II)

En general, aplicando el mismo procedimiento podemos darnos cuenta que si existe $2n+1$ puentes que comunican a $E$ con $E^c$, el número de veces que aparece la letra $E$ en la secuencia es $n + 1$.

Para nuestro caso tenemos:

$$2n + 1 = 7$$

$$2n = 7 - 1$$

$$2n = 6$$

$$n = 3$$

Apariciones de $E$ : $n + 1$, en nuestro caso $3 + 1 = 4$, tal como comprobamos en la figura 11.

Aplicando el anterior razonamiento al caso de los puentes de Königsberg, observamos lo siguiente (La notación $Ap(X)$ indica el numero de veces que aparece la letra $X$ en la secuencia):

Partiendo de $C$ y recorriendo sus puentes ($c$, $d$, $g$) una sola vez, las veces que aparece $C$ en la secuencia es $Ap(C) = n+1 = 1 + 1 = 2 ]$, ya que $2n + 1 = 3, n = 1$. La secuencia recorrida es $CACD$.

Partiendo de $A$ y recorriendo sus puentes ($a$, $b$, $c$, $d$, $e$) una sola vez, las veces que aparece $A$ en la secuencia es $Ap(A) = n+1 = 2 + 1 = 3$, ya que $2n + 1 = 5, n = 2$. La secuencia recorrida es $ABACAD$.

Partiendo de $B$ y recorriendo sus puentes ($a$, $b$, $f$) una sola vez, las veces que aparece $B$ en la secuencia es $Ap(B) = n+1 = 1 + 1 = 2$, ya que $2n + 1 = 3, n = 1$. La secuencia recorrida es $BABD$.

Partiendo de $D$ y recorriendo sus puentes ($e$, $f$, $g$) una sola vez, las veces que aparece $D$ en la secuencia es $Ap(D) = n+1 = 1 + 1 = 2$ ya que $2n + 1 = 3, n = 1$. La secuencia recorrida es $DACDB$. Afortunadamente no es el problema de los $50000$ puentes de Königsberg!!!.

Entonces, el numero total de veces que visitamos las islas es:

$$Total = Ap(C) + Ap(A) + Ap(B) + Ap(D)$$

$$= 2 + 3 + 2 + 2$$

$$= 9$$

Esto nos dice que para recorrer los puentes requerimos de $9$ letras para designar el recorrido.

Si comparamos los resultados obtenidos, vemos que son diferentes $(8 \neq 9)$ y entonces por reducción al absurdo queda demostrado que no se puede trazar un recorrido que pase una sola vez por cada uno de los puentes.