路线着色谜题

道路着色问题（Road Coloring Problem）是由班雅明．怀斯及罗伊．阿德勒提出，原意是找出地图指引及计算机自动除错程序的设计方式1970年提出，此后近四十年，许多数学家都试着找出解答，但都无功而返。

一位「高龄」六十三岁的以色列数学家却在去年底得出解答，尽管许多人讶异于他的成就，但他自己仍然低调表示，这只是个「数学家的本务」。

近40年来 大热门数学谜题

但没想到不但怀斯自己花了八年都无法解答，接下来三十年间一百多位数学家也束手无策。

这个难题的假设是，在出发点（圆点）及道路（直线）的数量都固定的情况下，应该有办法以不同颜色标示道路，让人不管从哪一个点出发，都能到达固定的点。这在真实生活中的情况就像是，不管朋友住在哪里，只要知道你家的位置，绕再远都有办法到你家。

以图为范本（见下图，取自维基百科），如果按照「蓝—红—红、蓝—红—红、蓝—红—红」的方式行走，不管从哪个点出发都能到黄色的点；如果是「蓝—蓝—红、蓝—蓝—红、蓝—蓝—红」，则一定能到绿点

自苏联返以 一度屈就守卫

这个看似简单的问题，最后碰到阿夫拉罕．塔克特曼（见上图，取自网络）才被解开。塔克特曼原居苏联，当时就已经是个小有名气的数学家。苏联瓦解后，他回归以色列，却因工作难找只好当个守卫，几经波折才重拾教鞭，于一九九五年到巴伊兰大学任教。

塔克特曼说，他花了一年才想通问题，去年拿着铅笔涂写八页才写完解答；结论在去年年底获得确认后，终于证明他的成就。但塔克特曼说他是完成了数学家该做的事，很幸运能被认可，他不会因此而被冲昏头。

(图形请点下面wiki维基百科就可以看到道路走法)

道路著色谜题图形请参照取自维基百科点选(英文全文):

In graph theory the road coloring theorem, until recently known as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze).[1] In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics.

The theorem was first conjectured in 1970 by Benjamin Weiss and Roy Adler.[2] It was proved by Avraham Trahtman in September 2007[3].

Example and intuition

The image to the right shows a directed graph on eight vertices in which each vertex has out-degree 2. (Each vertex in this case also has in-degree 2, but that is not necessary for a synchronizing coloring to exist.) The edges of this graph have been colored red and blue to create a synchronizing coloring.

For example, consider the vertex marked in yellow. No matter where in the graph you start, if you traverse all nine edges in the walk "blue-red-red—blue-red-red—blue-red-red", you will end up at the yellow vertex. Similarly, if you traverse all nine edges in the walk "blue-blue-red—blue-blue-red—blue-blue-red", you will always end up at the vertex marked in green, no matter where you started.

The road coloring theorem states that for a certain category of directed graphs, it is always possible to create such a coloring.

After 38 years, Israeli solves math code[Road Coloring Problem]

JERUSALEM - A mathematical puzzle that baffled the top minds in the esoteric field of symbolic dynamics for nearly four decades has been cracked — by a 63-year-old immigrant who once had to work as a security guard.

Avraham Trahtman, a mathematician who also toiled as a laborer after moving to Israel from Russia, succeeded where dozens failed, solving the elusive "Road Coloring Problem."

The conjecture essentially assumed it''s possible to create a "universal map" that can direct people to arrive at a certain destination, at the same time, regardless of starting point. Experts say the proposition could have real-life applications in mapping and computer science.

The "Road Coloring Problem" was first posed in 1970 by Benjamin Weiss, an Israeli-American mathematician, and a colleague, Roy Adler, who worked at IBM at the time.

For eight years, Weiss tried to prove his theory. Over the next 30 years, some 100 other scientists attempted as well. All failed, until Trahtman came along and, in eight short pages, jotted the solution down in pencil last year.

"The solution is not that complicated. It''s hard, but it is not that complicated," Trahtman said in heavily accented Hebrew. "Some people think they need to be complicated. I think they need to be nice and simple."

Weiss said it gave him great joy to see someone solve his problem.

Stuart Margolis, a mathematician who recruited Trahtman to teach at Bar Ilan University near Tel Aviv, called the solution one of the "beautiful results." But he said what makes the result especially remarkable is Trahtman''s age and background.

"Math is usually a younger person''s game, like music and the arts," Margolis said. "Usually you do your better work in your mid 20s and early 30s. He certainly came up with a good one at age 63."

Adding to the excitement is Trahtman''s personal triumph in finally finding work as a mathematician after immigrating from Russia. "The first time I met him he was wearing a night watchman''s uniform," Margolis said.

Originally from Yekaterinburg, Russia, Trahtman was an accomplished mathematician when he came to Israel in 1992, at age 48. But like many immigrants in the wave that followed the breakup of the Soviet Union, he struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995.

The soft-spoken Trahtman declined to talk about his odyssey, calling that the "old days." He said he felt "lucky" to be recognized for his solution, and played down the achievement as a "matter for mathematicians," saying it hasn''t changed him a bit.

The puzzle tackled by Trahtman wasn''t the longest-standing open problem to be solved recently. In 1994, British mathematician Andrew Wiles solved Fermat''s last theorem, which had been open for more than 300 years.

Trahtman''s solution is available on the Internet and is to be published soon in the Israel Journal of Mathematics.

Joel Friedman, a math professor at the University of British Columbia, said probably everyone in the field of symbolic dynamics had tried to solve the problem at some point, including himself. He said people in the related disciplines of graph theory, discrete math and theoretical computer science also tried.

"The solution to this problem has definitely generated excitement in the mathematical community," he said in an e-mail.

Margolis said the solution could have many applications.

"Say you''ve lost an e-mail and you want to get it back — it would be guaranteed," he said. "Let''s say you are lost in a town you have never been in before and you have to get to a friend''s house and there are no street signs — the directions will work no matter what."