The Seven Bridges of Königsberg
The Seven Bridges of Königsberg is a classic Mathematical problem first resolved by Euler in 1736. It refers to the town of Königsberg where seven bridges were built for residents to access different areas of the town. People started wondering whether it would be possible to take a walk around and use each bridge a single time to return to the same spot.
I’ll tell you right now: you can stop trying to find a path. There isn’t one. But what is interesting is why.
This takes us into an area of math called graph theory. Graph theory has nothing to do with what you may be used to thinking of as a graph, typically in the context of statistics. In this context, a graph refers to a collection of vertices (points) that are connected by edges (lines). You’ve probably encountered some before in this type of puzzle:
You may be asking what this has to do with the seven bridges of Königsberg. In short, everything. The map can be redrawn to look like the graphs above.
The secret to these problems lies in counting lines. If you look at each vertex individually, you can count the number of lines coming in and out of it. Pick one (any one) to try to start your path. No matter how many bridges there are, you will need to exit and enter it an even number of times (one exit for each entrance). Since each vertex has an odd number of lines (3, 5, 3, and 3), that won’t be possible. You’ll keep getting stuck at one vertex without a way out.
If you don’t plan to come back to the point where you started, then two of the vertices can have an even number of lines connected to them (where you start and where you end your path), but even that isn’t the case here.
Go back to the other puzzles and see if you can solve them now. The two top ones are possible but the bottom one is not because, just like with the bridges, each vertex has an odd number of lines connected to it.
Try this brain teaser next: Are You Smart Enough to Work for Google?
Facebook comments