Subscribe to Print Edition | Sat., March 22, 2008 Adar2 16, 5768 | | Israel Time: 00:34 (EST+7) web haaretz.com   Back to Homepage Rosner's Domain Diplomacy Defense Jewish World Opinion National Print Edition Advertising Books Arts & Leisure Business Real Estate Easy Start Travel Week's End Anglo File

Last update - 21:27 20/03/2008 Israeli ex-security guard solves 38-year-old math problem By The Associated Press Tags: israel, road coloring problem  A mathematical mystery that has baffled top minds in the field of symbolic dynamics for nearly four decades was cracked last year by a 63-year-old former Israeli security guard. Avraham Trakhtman, a mathematician who worked as a laborer after immigrating to Israel from Russia, succeeded in solving the elusive Road Coloring Problem. The conjecture assumes that it is possible to create a universal map that would direct people to arrive at a certain destination, at the same time, regardless of their original location. Experts say this proposition, which seems to defy logic, could actually have real-life applications in the fields of mapping and computer science. "In math circles, we talk about beautiful results. This is beautiful and it is unexpected. Even in layman's terms it is completely counterintuitive, but somehow it works," said Stuart Margolis, a colleague who recruited Trakhtman to Bar Ilan University near Tel Aviv. Advertisement "The first time I met him he was wearing a night watchman's uniform," said Margolis. 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. Weiss said he believed that given a finite number of roads, one should be able to draw up a map, coded in various colors, that would lead to a certain destination regardless of the point of origin. For eight years, he tried to prove his theory. Over the next 30 years, some 100 other scientists attempted to as well. All failed, until Trakhtman jotted solved it in eight pages in pencil last year after working on it for twelve months. Originally from Yekaterinburg, Russia, Trakhtman was already an accomplished mathematician before he came to Israel in 1992, at the age of 48. But like many immigrants in the wave that followed the breakup of the former Soviet Union, he struggled to find work and ended up employed in maintenance and security before landing a teaching position at Bar Ilan in 1995. Trakhtman says he was lucky to be recognized, but plays down his recent achievement. "The solution is not that complicated. It's hard, but it is not that complicated," he said. "Some people think they need to be complicated. I think they need to be nice and simple." Trakhtman's solution is available for viewing on the Internet and will soon be published in the Israel Journal of Mathematics. Weiss said it gave him great joy to see someone solve his problem. Joel Friedman, a math professor at the University of British Columbia, said probably everyone in the field of symbolic dynamics has tried to solve the Roadmap Coloring Problem at some point, as well as experts in related disciplines graph theory, discrete math and theoretical computer science. Trakhtman's achievement is not the longest open problem ever solved. In 1994, British mathematician Andrew Wiles solved Fermat's last theorem, which had been open for more than 300 years. Margolis says 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," he said. Bookmark to del.icio.us   Declassifying AIPAC Two former pro-Israel lobbyists charged with revealing secret info. to Israeli diplomats. Jersualem pilgrimage Christian pilgrims flock to Holy City to mark Good Friday and retrace the route of Jesus.   1.   Mr Trakhtman 22:23  |  Big Sooz 20/03/08   2.   No clue so I have to believe it. Would it work on 22:28  |  Karl 20/03/08   3.   Great man!! If only this country checked better olim potential!! 23:17  |  Alain 20/03/08   4.   Karl#2 23:23  |  jens 20/03/08   5.   Great Potential 23:40  |  Igor 20/03/08   6.   It wouldn`t work if. . . . 00:03  |  MichaelF 21/03/08   7.   millions!! 01:18  |  sam 21/03/08   8.   Andrew Wiles solved Fermat`s last theorem- not solved- there was 01:23  |  sara 21/03/08   9.   JENS!!! 01:35  |  Will 21/03/08   10.   Cool! 02:20  |  Haldrik 21/03/08   11.   Avraham Trakhtman 02:26  |  Andy Samson 21/03/08   12.   Great Story - Nothing to do with Israelis! 03:30  |  H. Kolter 21/03/08   13.   This a month old story, Haaretz picked it up only now 04:22  |  Genuine Tosefta 21/03/08   14.   Avraham the Genius 04:52  |  Michael J 21/03/08   15.   A genius, a yiddisha cup. 12:24  |  petra 21/03/08   16.   Jens, great. I admit hereby you were far better than me. See 17:14  |  Karl 21/03/08   17.   Great. There are some great Irish matematitians in NY as well... 03:59  |  Yaakov Sullivan 22/03/08   18.   Directions to God 05:26  |  Ginger 22/03/08   19.   Russians coming 10:34  |  the Pope 22/03/08   20.   and.. nothing good comes from you petra 10:39  |  Puhi 22/03/08   21.   Ginger (18) to hot for my stomach but what about 21:43  |  Karl 22/03/08

Today Online Bradley Burston: Macho U.S. Jews, pantywaist Israel Responses: 208 Jewish group seeks to purge YouTube of anti-Semitic videos Responses: 197 PM says worried Russian weapons will reach Hezbollah Responses: 107 Israel, Germany plan int'l summit to stop Iran nuke program Responses: 114 13-year-old boy wounded in terror attack near Hebron Responses: 103 Editorial: J'lem yeshiva massacre must not lead to boycott of Israeli Arabs Responses: 97 Rosner's Domain U.S. govt. to appeal ruling on classified material in AIPAC trial I've known my rabbi for more than 20 years... (WTR) Poll: Mideast summit in Moscow, a good idea? There's no need for American pressure on Israel Jewish connections in the NCAA (WTR) More Headlines 00:21 Hezbollah deputy chief says he has proof Israel killed Mughniyah 00:14 Cheney in J'lem: U.S. will never pressure Israel to take security risks 20:31 Yemen FM: Progress made in Hamas-Fatah reconciliation talks 19:20 2 Qassams hit Israel as Egypt hosts Hamas, Jihad for truce talks 12:45 Body of Palestinian pulled from collapsed Egypt-Gaza tunnel 12:23 Police arrest 2 youths suspected of stoning cars on Wadi Ara road 01:25 Christian pilgrims flock to Jerusalem's Old City for Good Friday 09:16 Ex-prof with alleged terror ties refuses to testify in U.S. court 06:56 Umm al-Fahm resident shot to death outside her home 17:51 U.S. gov't to appeal ruling on classified material in AIPAC trial 16:11 Israel, Russia finalize deal on supply of armored vehicles to PA 21:30 German Jewish leader raps Pope over prayer for conversion of Jews Previous Editions Select Day 21 mar 20 mar 19 mar 18 mar 17 mar 16 mar 14 mar 13 mar 12 mar 11 mar 10 mar 09 mar

Special Offers Advertisement FAREWELL ISRAEL New Film The Coming War for Islamic Revival - View Movie Trailer READY FOR PURIM? BUT - Who Will Guard The Hamentasch? Free the Palestinians from: Corrupt Kleptocracy, Tyrannical Theocracy, Abysmal Anarchy Long-term Israel programs MASA is your gateway. More programs. More grants. NEW! Dan Boutique Jerusalem Hotel Hip Dan Hotel in Jerusalem. Attractive Introductory Rates 7589 rockets fired so far HELP US TO HELP THEM FREE JEWISH HISTORY COURSE Berel Wein's best selling lectures. 5000 Years in Five hours /CD/MP3 Marina Royale Herzelia Pituach Your Luxurious Suite While Staying in Israel Fattal Hotel Chain Perfectly located hotels on best resorts of Israel. ISRAEL BONDS Build Israel Israel bonds - a multi-purpose way to celebrate Israel's 60th Eldan Rent a Car Israel's leading car rental company offers you a 20% discount on all online reservations Junkyard Junk a car - get free towing nationwide and a tax-deductible receipt

Home | TV | Print Edition | Diplomacy | Opinion | Arts & Leisure | Sports | Jewish World | Underground | Site rules |

Haaretz.com, the online edition of Haaretz Newspaper in Israel, offers real-time breaking news, opinions and analysis from Israel and the Middle East. Haaretz.com provides extensive and in-depth coverage of Israel, the Jewish World and the Middle East, including defense, diplomacy, the Arab-Israeli conflict, the peace process, Israeli politics, Jerusalem affairs, international relations, Iran, Iraq, Syria, Lebanon, the Palestinian Authority, the West Bank and the Gaza Strip, the Israeli business world and Jewish life in Israel and the Diaspora.

© Copyright  Haaretz. All rights reserved