Road Coloring Problem Solved

ArieKremen writes "Israeli Avraham Trakhtman, a Russian immigrant mathematician who had been employed as a night watchman, has solved the Road Coloring problem. First posed in 1970 by Benjamin Weiss and Roy Adler, the problem posits that given a finite number of roads, one should be able to draw a map, coded in various colors, that leads to a certain destination regardless of the point of origin. The 63-year-old Trakhtman jotted down the solution in pencil in 8 pages. The problem has real-world implementation in message and traffic routing."

Bad timing.

[Rob T Firefly]

Unfortunately for him, a cheap, safe, mass-market flying car was announced an hour later.

Re:Yeah, yeah, First Post, but...

[notgm]

not fast, but reliable. if you don't care what time you get in to cleveland, this guarantees you'll never *end* up in pittsuburgh.

wait, ohio to cleveland?

Re:The writeup is misleading

[Anonymous Coward]

The guy is actually a mathematician who had to work as a security guard right after he immigrated to Israel, which is common for most immigrants. This guy had lots of formal training solving equations like this.

Well I guess it is not surprising that he solved this problem. As a security guard I'm sure he had to figure a way to motivate people to go the exit regardless of where they started from. He was actually probably solving a harder problem in his head. Each of those colors probably symbolizes a certain motivator that he had to use in his job. Yellow is being yelled at, green is the nightstick, and red is the pepper spray.

Re:Actually

[spookymonster]

Actually, if he were to put it on a SD card, it'd take up less than 1 square inch...

Where's my PEDANTIC:-1 option?

Re:Night Watchman?

[Yvanhoe]

In Soviet Russia they say that because Americans were so poor mathematicians, they had to invent the computer...

HIRED!

[TheGreatOrangePeel]

Well, SOMEONE is about to be hired by google... ...you suppose it's too late to learn Russian, and become his friend?

Re:OK, but...

[KDR_11k]

Forty-two.

Washington - RNC ???

[zappepcs]

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

I wonder if this can be retroactively applied to certain email servers in Washington?

Re:Night Watchman?

[rev124]

In Soviet Russia computer invents you!

...ugh, that was stupid.

Re:Old news?

[huckamania]

Apparently his proof was published last September. It's "news" because it's just now hitting the semi-mainstream press. You people fail at nerddom.

No, they're just applying the normal slashdot skepticism. The guy was a security guard for crying out loud. And he's old. Really old. No way he could have used his brain to solve something involving math. Besides, he's probably only trying to get seed money so he can start a pyramid scheme selling perpertual motion.

Re:Night Watchman?

[nomadic]

In Soviet Russia they say that because Americans were so poor mathematicians, they had to invent the computer...

I hear that Russians are such poor computer scientists, they had to get good at math...

so..

[g0dsp33d]

That means my screensaver could be an Internet network diagram?

Re:Old news?

[Reason58]

But when you get to that point, it loses all meaning. R on Lincoln L on 1st St L on R Ave R on Prescott How is that any harder than saying: Orange Burnt Amber Sanguine Desire Ghost Egg White Not to mention the more complicated the street system the more colors you would need and that would cause extreme confusion as people try and tell shades apart.

Re:Sign of a true Genius.

[Jamil Karim]

The man is a True Genius.

Real Men of Genius!
Today, we salute you, Mr. former-nightwatchman-turned-mathmetician!

Re:Yeah, yeah, First Post, but...

[ColdWetDog]

Yah..I thought the airlines solved this long ago with their baggage systems.

What airlines have you been using lately? Not the ones I fly, certainly.

Re:Night Watchman?

[Anonymous Coward]

s/The ^H^H^H joke became lame in like 1994. Seriously, just stop./Awesome, dude! Like, retro 1994 awesomeness! Keep on truckin'!/

Fixed it for you.

I knew it!

[Teilo]

Proof at last, that that guy who kept saying, "You can't get there from here" is a bloody liar.

and the evil professor says ...

[B3ryllium]

Now adjust the algorithm for colour-blindness! :)

Show your work.

Didn't AAA solve this long ago?

[rholland356]

I clearly remember my parents getting Triptick maps from AAA for our annual sojourn to Florida. Those multipage maps had roads colored in nicely, and you just followed them to your destination.

Have mathematicians scraped the bottom of the barrel for unsolved puzzles? Oh, damn. I think I just created something for mathematicians to ponder for the next few decades...

In related news ....

[PPH]

Based upon his ground-breaking research on the road coloring problem, night watchman Trakhtman has been promoted to the Department of Transportation pavement striping crew.

Re:Night Watchman?

[Applekid]

It's way better to be good at math, though, if you have to pick one. Sure, computers are quite practical for solving difficult problems, but you don't get nearly as much insight from simulation as you do from deriving an analytical formula for something (assuming such a formula is possible).

True, but the math needed to draw one frame of Doom alone took me a week, and I still haven't finished filling the boxes on my sheet of graph paper.