What’s the fastest route for navigating a maze? You don’t know, and that’s alright. You’re not a genius, aren’t you? Never mind! The real world is sort of like a maze, and finding your way around could be frustrating as it is through a maze.
This was a real-life situation for the people of a certain town back in the 18th century. The town was scattered along a winding river which had seven bridges that connected it’s suburbs. Inhabitants thought of such a clever means to navigate their town without crossing all seven bridges — but that didn’t go so well, though. However, this problem was eventually never solved, but it led to one of the greatest math theories of all time. Dear friends, welcome to Königsberg (present day Kaliningrad, Russia), the infamous town that led to the Königsberg puzzle.
Related media: How The Königsberg Bridge Problem Changed Mathematics
Many Rivers To Cross
Königsberg was a small town built along the banks of the River Pregel (present day River Pregoya), which virtually chopped the town into four distinct landmasses; aforementioned, it had seven bridges connecting all four landmasses. Legend has it that, inhabitants had a popular pastime during Sunday afternoons, if they could find a route to navigate their town without having to cross any bridge twice — that is, roam the entire town by crossing every bridge just once. Spoiler alert: nobody was ever able to pull off that stunt, but that didn’t mean it was impossible.
It only required a genius to crunch some geometry to figure it out. In 1735, this problem prompted Carl Leonhard Gottlieb Ehler, then the mayor of Danzig, a city some 129 kilometers (80 miles) west of Königsberg, who consulted the renowned mathematician Leonard Euler with the problem on behalf of Heinrich Kühn, a local mathematics professor in Königsberg. Euler later published his first book on mathematics a year into this correspondence, and would later go on to publish more than 500 books and papers over the course of his lifetime.
At first, Euler thought this problem was way beneath his math prowess, in a statement, he wrote:
“… thus you see, most noble Sir, this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.”
At long last, Ehler and Kühn convinced Euler by making him realize that this problem was a whole new mathematical phenomenon: “The Geometry of Position,” this is what is known as topology today. Topologically, the exact layout of the plane figure doesn’t matter — a popular math joke that says a topologist can’t tell the difference between toroids, say a donut, and the rim of a coffee mug. Fair enough! This new mathematical phenomenon was only paperwork; no one hadn’t really crunched the numbers and applied it yet.
And Bridges Too Far Out To Cross
The seven bridges of Königsberg was a perfect example for this concept since there was no need to really do any precise measurements or calculations. You could easily map out the town into a simple diagram without losing track of whatever it meant. Obviously, anyone would attempt trying to solve this problem by mapping out all possible routes throughout the town. That’s what you thought, didn’t you? But Euler thought otherwise: he noticed that that strategy would waste time and perhaps (you guessed it) wouldn’t be applicable to other places.
In short, what if another town had say ten bridges or more. For a clever approach, Euler ignored the whole idea of bridges for a moment and just labeled the landmasses: land A, land B, land C, and land D. This way, he could easily represent a journey from ‘A’ to ‘B’ as ‘AB,’ and a journey from ‘A’ to ‘B’ to ‘C’ as ‘ABC,’ for instance. (In his approach, the bridges being crossed doesn’t matter). Its essential to take note that the number of letters in a journey is one more than the number of bridges crossed. For instance, an ‘AB’ journey crosses one bridge, an ‘ABC’ journey crosses two, and on.
Euler again realized that Königsberg had seven bridges, and eight letters would be needed for a seven-bridge journey, so the solution to the problem required eight letters. Next, he came up with a general rule with a simplified diagram. If there were only two landmasses, say ‘A’ and ‘B,’ and you crossed bridge ‘A’ once, then ‘A’ would either be where your journey begins or ends — thus you’d land on ‘A’ exactly once. And if you cross bridges ‘A,’ ‘B,’ and ‘C’ one time apiece, then you’d land on ‘A’ exactly twice.
Here’s the rule of thumb: If you have an odd number of bridges to a landmass, you can add one to that number and divide by two to get the number of times that landmass needs to be landed upon in the journey. (With this rule at hand, if you add one to three its equals four, divided by two gets you two, that’s number of times you’d land on ‘A’). Now back to the matter: if there are five bridges that leads to ‘A,’ it will be crossed thrice in the eight-letter his solution. Land B,’ ‘C,’ and ‘D,’ all have two bridges leading to them, so they’ll appear twice.
Now here’s the catch: 3 + 2 + 2 + 2 is 9, not 8, though you must land on eight landmasses for seven bridges. Spoiler: roaming through Königsberg by crossing each bridge once was impossible. Ta-da!
You Just Can’t Find A Way Through
However, Euler didn’t give up. He later came up with a more general rule for other town with different number of bridges. Let’s say a town has an odd number of bridges, then you can figure out whether you can make the journey or not. If the sum of the number of times each letter must appear is one more than the number of bridges — like the eight-letter solution aforementioned — you can make the journey; but if the sum is greater than that, then we’re sorry you can’t.
What if its an even number of bridges? It depends on where you’ll start. Let’s say you start on landmass A and cross two bridges, you’d land on ‘A’ twice in your solution; and if you start on the other side, then you’d land on ‘A’ only once. But if there are four bridges, then you’d land on ‘A’ thrice if it’s the starting point, and twice if it’s not. What this means is that, for a general rule, if your journey doesn’t start on ‘A,’ then you’d land on ‘A’ half the frequency as the number of bridges (four bridges divided by two equals two times); but if your journey does start on ‘A,’ then you’d land on ‘A’ half the frequency plus one (four bridges divided by two plus one equals three times).
It seems we’ve given you too much thinking than crossing. Sorry! But the brilliance of Euler has led to so much than just crossing bridges. His methods led to one of the first examples of graph theory — an essential area of mathematics that applies network theory to the world of navigation, social, and electronic networking today. Königsberg eventually added another bridge, rending Euler’s solution useless, and later, much of the town was destroyed by British forces during World War II. But that weird river-logged town revolutionized a whole new branch of mathematics.
Read more facts like this one in your inbox. Sign up for our daily email here.
The Factionary is ever ready to provide you with more interesting content for your reading pleasure. If you’re amazed by our work, you can support us on Patreon by a donation fee of your choice. Thank you!
Written by: Nana Kwadwo, Thu, Jun 06, 2019.
One comment