The Road Coloring Problem Solved

The Road Coloring problem has been a long-standing mathematical problem. And it has been solved by a 63 year old man who lives in Israel, called Avraham Trakhtam.

Basically by solving the problem, now it is possible to give someone a set of universal directions to get them to arrive to an specific spot. This can be used in mazes as well as when giving directions to find a restaurant in a city. For a better explanation let’s see what Wikipedia has to say:

The Road coloring conjecture, also referred to as the Road coloring problem, is a theorem in graph theory with implications in symbolic dynamics. It deals with synchronized instructions. The issue involved is whether by implementing such instructions, one can reach or locate an object or destination when lost within a city, maze, or network. Using this theorem, for example, it would be possible to produce a set of directions that would lead you to a friend’s house even if you are completely lost in the city in which he lives and there are no street signs.

Pretty interesting. The story of Avraham is also interesting, he was a migrant who arrived from Russia with nothing. Working as a labourer and night watch. Now he has made history in maths.

The problem was first posed in 1970 by Benjamin Weiss. It took Traktham a year to solve the problem.

“The solution is not that complicated. It’s hard, but it is not that complicated. Some people think they need to be complicated. I think they need to be nice and simple.”

I totally agree with him. Most great things in life are simple and he has proven it once again. Let’s see how this knowledge will integrate into our everyday lives.

Those were the news on the road coloring problem

Technorati Tags: road coloring problem, Avraham Trakhtam, israel, maths

Please click here for more recent posts.

Mar200821

admin

0