Israeli Immigrant Solves Elusive 38-Year-Old Math Puzzle

[Rage for Order]

http://news.yahoo.com/s/ap/20080320/ap_on_re_mi_ea/israel_math_riddle

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.


I'm no math whiz, but this is pretty cool

[Rage for Order]

1. More from the link:

"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."

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.

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.

(Stuart) Margolis (a mathematician who recruited Trahtman to teach at Bar Ilan University near Tel Aviv) 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."

[NuttyFluffers]

4. *snort* "Let's say you are lost in a town you have never been in before...."

"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."

.... except in Tokyo.

[sharesunited]

2. I've lost the remote again.

Get me Trahtman.

[papau]

3. so we no longer need a GPS to get to a friends house? The problem (below) is hard for me to

even understand how to start working on a solution - damn good thing I learned early on I was only smart enough for applied math

Suppose we are given three cities A,B,C, and we are given roads (AB), (AC), (BA), (BB), (CB), (CC).
(The first is a road from A to B; etc).
We decide to color roads (AC), (BB), (CB) green, and color (AB), (BA), (CC) red.
Now when someone calls up and asks to get to B, we tell him to take two green roads.
If he asks to get to another city, say C, we first direct him to B and then from B to C; so we tell him "Green Green Red Green".
You can check for yourself that no matter where he starts, these directions get him to C.