Whether you are timing to check how quickly you can fill your coffee maker or simply counting your steps to the bus stop in the morning, there is something about the monotony of everyday life that makes us try to turn it into a game. The inhabitants of the Prussian city of Konigsberg of the eighteenth century (now, as you know, this is Kaliningrad) were the same as all of us. It was just the game they played with seven bridges in their city that one day sparked the interest of one of the greatest mathematicians in human history.
Konigsberg was built on the banks of the Pregel (Pregolya) River, which divided the city into four separate residential areas. People moved from one area to another through seven different bridges. According to legend, a popular pastime during Sunday walks was to try to cross the entire city so as to cross each bridge only once. Nobody has figured out how to do this, but this does not mean that the problem has no solution. They just had to go to the right expert to get to know him.
In 1735, the mayor of the city of Danzig (now the Polish Gdansk), located 120 kilometers west of Konigsberg, Karl Leonard Gottlieb Ehler, wrote to Leonard Euler with a letter in which he asked for help in solving this problem on behalf of a local professor of mathematics named Heinrich Kuehn. Even then, Euler was a famous and highly successful mathematician - he published his first book within a year after this letter, and in his entire life he wrote more than 500 books and articles.
Therefore, it is not surprising that at first Euler thought that it was beneath his dignity to deal with this problem, and wrote in response: “So, you see, esteemed sir, this type of solution has practically nothing to do with mathematics, and I do not understand why you are dealing with such a request to a mathematician and not to someone else, since the decision is based only on common sense and does not depend on any of the known mathematical principles."
Ultimately, however, Ehler and Kühn succeeded in convincing Euler, and he realized that this was a completely new type of mathematics - the "geometry of positions", today known as topology. In topology, the exact shape or location of an object does not matter. There is even an old joke that a topologist cannot tell the difference between a donut and a coffee cup, since both items have exactly one hole. Until then, this completely new area of mathematics was only written about, but no one yet understood what problems it could solve. The seven Konigsberg bridges were excellent experimental confirmation of the new theory, since the problem did not require any measurements or precise calculations. You can turn a complex city map into a simple and understandable graph (diagram) without losing any important information.
While one might be tempted to solve this problem by mapping out all possible routes through the city, Euler immediately realized that this strategy would take too long and would not work with other similar problems (what if in another city there were, say, twelve bridges?). Instead, he decided to temporarily distract himself from the bridges and marked the land areas with the letters A, B, C and D. Thus, he could now describe the journey across the bridge from area A to area B as AB, and the journey from area A through area B area D as ABD. It is important to note here that the number of letters in the route description will always be one more than the number of bridges crossed. So, route AB crosses one bridge, and ABD crosses two bridges, and so on. Euler realized that since there are seven bridges in Konigsberg, in order to cross them all,the route must consist of eight letters, which means that the solution of the problem will require exactly eight letters.
Then he came up with a more general rule using an even more simplified scheme. If you had only two land sections, A and B, and crossed the bridge once, then section A could be where the journey began or where it ended, but you would be in section A only once. If you crossed bridges a, b, and c once, you would be on section A exactly twice. This led to a handy rule: if you have an even number of bridges leading to one piece of land, you must add one to that number, and then divide the total by two to figure out how many times that section should be used during your journey. (in this example, adding one to the number of bridges, that is, to 3, we get four, and dividing four by two we get two,that is, it is exactly twice during the journey that section A) is crossed.
Promotional video:
This result brought Euler back to his original problem. There are five bridges that lead to Section A, so the eight-letter solution he is looking for will have to be crossed three times. Sections B, C and D have two bridges that lead to them, so each must cross twice. But 3 + 2 + 2 + 2 is 9, not 8, although according to the condition you need to go through only 8 sections and cross 7 bridges. This means that it is impossible to go through the entire city of Königsberg using each bridge exactly once. In other words, in this case the problem has no solution.
However, like any true mathematician, Euler did not stop there. He continued to work and created a more general rule for other cities with a different number of bridges. If the city has an odd number of bridges, then there is a simple way to find out if you can make such a trip or not: if the sum of the number of occurrences of each letter denoting a piece of land is one more than the number of bridges (as, for example, in the eight-letter solution, about mentioned earlier), such a journey is possible. If the sum is greater than this number, it is impossible.
What about an even number of bridges? In this case, it all depends on where to start. If you start at Section A and travel across two bridges, A appears twice in your solution. If you start on the other side, A will appear only once. If there are four bridges, then A appears three times if this section was the starting point, or twice if it was not. In general terms, this means that if the journey does not start from section A, it must be crossed twice as many times as the number of bridges (four divided by two gives two). If the journey starts from section A, then it must intersect one more time.
The genius of Euler's solution lies not even in the answer, but in the method he applied. It was one of the earliest use cases of graph theory, also known as network theory, a highly sought after field of mathematics in today's world filled with transportation, social and electronic networks. As for Königsberg, the city ended up with another bridge, which made Euler's decision controversial, and then British forces destroyed most of the city during World War II. Today both the city and the river have new names, but the old problem lives in a completely new field of mathematics.
Igor Abramov