Saturday, April 14, 2007

My Favorite Lenny in Funky Kingstown

Today we have a new chapter in the continuing story of just how clever My Favorite Lenny was. Konigsberg (German for King’s Town) was built on a river with two islands in the middle. There were seven bridges connecting the two islands and the two river banks, as shown in the picture above. A pastime in the town was to walk the city with the idea of crossing every bridge exactly once; jumping in the river to avoid using a bridge twice was not allowed. No one had ever solved the problem, but that didn’t mean it was impossible, did it. Lenny to the rescue!

Euler changed the city map into what we now call a graph, a collection of dot and lines connecting the dots, known to mathematicians as vertices and edges. The graph above represents Konigsberg. We will define the degree of a vertex as the number of edges it has connecting it to other vertices. Here are the degrees for all the vertices.

Degree(A) = 5
Degree(B) = 3
Degree(C) = 3
Degree(D) = 3

Euler figured out that trying to solve a problem like this was all about even and odd degrees. If every vertex has even degree, we can cross every bridge and even end up where we started; if there are exactly two vertices that have odd degree, we will be able to start at one of them and cross every bridge, ending up at the other vertex of odd degree. But if there are more than two vertices of odd degree, game over, man. That is the situation in Funky Kingstown, and that’s why no one had ever been able to do it.

My Favorite Lenny.

No comments: