Russian immigrant solves math puzzle

This story sort of provides one with hope that nothing is impossible.

A 63-year-old mathematics professor at Bar-Ilan University, who worked as a guard for about five years after his aliya from the former Soviet Union in 1990, has solved an abstract math problem that has befuddled experts for the last 38 years.

Prof. Avraham Trakhtman finally found the solution, which will be published in a few months in the Israel Journal of Mathematics, solely by tossing it around in his brain and using a pencil and paper. His research, which has already been placed on a Web site for professionals and is available for download, has elicited much excitement among mathematicians in the esoteric field.

Trakhtman solved the "Road Coloring Problem," which was raised by Israeli mathematics Prof. Binyamin Weiss and others in 1970. There are many forms but the most popular one among experts goes like this:

A man reaches a town he has never visited before and drives around trying to find the home of his friend even though there are no street names. The friend says not to worry and that he will provide instructions (left, right, left...) on how to get there.

This is called synchronizing instruction. The problem is whether by using such instructions, the driver could reach his destination no matter where he was lost, said Prof. Stuart Margolis, a colleague and mentor of Trakhtman who made aliya from the US and joined Bar-Ilan the same year as the Russian mathematician.

"He is brilliant with a high IQ," Margolis told The Jerusalem Post. "It's God-given gray matter in his brain. He is shy, reserved and very modest. He intentionally offered his paper to an Israeli journal even though any mathematics journal in the world would be overjoyed to get it. Now he's working on a real algorithm to implement his solution."

There is also a computer version of the problem: One has a big network like the Internet, and an e-mail message is lost somewhere. The systems operator wants to get it sent to the right place, said Margolis. "But he doesn't know where it is. Synchronizing instructions could get it there, like a mouse through a maze. Avraham's work proves that it's always possible to find one's way with such instructions."

Trakhtman's colleagues, who were following his instructions, could quickly see that his solution was correct as he prepared proofs with paper and pencil. Nevertheless, it still must go through the referee process.

Via Jerusalem Times.