63-year-old solves riddle from 1970

Israeli mathematician unravels puzzle that baffled scientists for decades
By Aron Heller
The Associated Press
updated 5:06 p.m. CT, Thurs., March. 20, 2008

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.

/quote

There's a bit more at the link, although despite asserting that the "solution" is "on the web" they don't give a clue as to where.

¹ In the real world it's well known that one can arrive at an intended destination by following directions that do not include a starting point. This is, in fact, the system used by one aircraft manufacturer of my acqauintance, where in order to determine what part(s) are in use on the airplane one follows the "changes" without knowing what the original configuration was.

In this case, I "pulled" a minimum of about 300 drawings, and an average of about 425, for each of about 80 "problem squawks," in order to learn that previous engineers who had previously responded to the same pilot/shop complaints had "fixed" each of several parts and had indeed made perfectly fine "fixes" - but to parts that were not used on the airplane. Some "problems" had been fixed 8 consecutive times without ever being applied to parts in use.

Perhaps if I'd had this solution I might still work there (but I doubt it).

John