Examples of famous problems resolved easily

Have there been examples of seemingly long standing hard problems, answered quite easily possibly with tools existing at the time the problems were made? More modern examples would be nice. An example could be Hilbert’s basis theorem. Another could be Dwork’s p-adic technique for rationality of zeta functions from algebraic varieties.

Answer

I’m sure there are loads. One that comes to mind is the Seven Bridges of Konisberg problem.

http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

Seven Bridges of Konisberg Illustration from Wikipedia

Basically, the problem asked: is there a path which you can walk such that you cross every bridge once and only once. (you can’t do things like walk halfway onto a bridge and walk back).

It was kinda known, well… conjectured, that there was no solution to this problem. Basically because no one found a solution to this problem and no one could prove why or why not.

Until Euler of course. As usual, it is always Euler who saves the day. He showed that there was no answer to this problem, as in, it was impossible to construct a path such that you cross every bridge just once.

The justification ended up being really simple: First, you have to put the problem in terms of the areas in town as opposed to the bridges. From the illustration, you can see that you can split the town into 4; the top, the bottom, the right and the center. Also, you have to realize that in order not to reuse a bridge, every region in town must have an even number of bridges (an entry bridge and an exit bridge). If you don’t have an even number of bridges, you get stuck in one of the regions (As in, if there’s just 1 bridge, you use that bridge and then get stuck. If there are 3 bridges, you go in through one, go out from the second, and then get stuck upon using the third). So, if you look closely, the regions have all odd numbers of bridges connecting them. (3 connecting to the top region, 5 connecting to the center, 3 connecting to the right and 3 connecting to the bottom)

Therefore, from this you get the idea of eulerian cycles and from there loads of properties of graphs and then graph theory was born. And if it were not for graph theory we’d be lost when it comes to the telephone network and the internet. So, yeah, long-standing problem with a simple solution and with even more long-standing benefits.

Acknowledgment: About the problem, another possibility would be if you had only 2 regions with an odd number of bridges connecting them, and all the rest must have an even number of bridges. The logic behind this would be that one of those two regions would be your “starting” point and the other would be you “ending” point or finish line. In this case, you would get an Eulerian path instead of a cycle

Attribution
Source : Link , Question Author : Turbo , Answer Author : TheSeamau5

Leave a Comment