Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Road Coloring Problem Solved

kdawson posted more than 6 years ago | from the hard-but-not-complicated dept.

Math 202

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

cancel ×

202 comments

Sorry! There are no comments related to the filter you selected.

XKCD (-1, Offtopic)

MiharuSenaKanaka (1080135) | more than 6 years ago | (#22818390)

So this is what today's XKCD was about...

Re:XKCD (5, Informative)

Anonymous Coward | more than 6 years ago | (#22818498)

No, today's XKCD is about the traveling salesman problem. They are very different.

Re:XKCD (0, Offtopic)

MiharuSenaKanaka (1080135) | more than 6 years ago | (#22818534)

Aha. Whoops. Colored paths, colored roads... close enough!

Re:XKCD (3, Informative)

Jawbreaker4Fs (974108) | more than 6 years ago | (#22819442)

Yeah... this would only apply to the XKCD comic if the road coloring problem was NP-complete.

Re:XKCD (1)

popmaker (570147) | more than 6 years ago | (#22820266)

Imagine THAT! If it was NP-complete, ALL NP-complete problems would be solved. Now THAT would be a major breakthrough.

You know what that means right? We could finally make a computer play a perfect game of tetris!

Night Watchman? (0, Flamebait)

ePhil_One (634771) | more than 6 years ago | (#22818406)

The guy was an accomplished Russian Mathmetician before he emmigrated from Russia 15 years ago.

Personally, I'm not surprised he's Russian, Mathemetics has seemed to be a strong point in that country, since their computers lagged behind us they had to make it up w/ mathmatical ingenuity.

Re:Night Watchman? (0, Insightful)

Anonymous Coward | more than 6 years ago | (#22818556)

And knowing the stupidity and exclusiveness in the USA about academics.....

He will stay a night watchman, because he does not have a USA degree and therefore shunned by the snooty upper educational society we have here.

It's pure bullshit how the USA punishes the educated that emigrate here that obviously are highly educated, but because they did not go to a "blessed" institution, you get to cook doughnuts instead of using that 12 year education in genetics. I know asian guys that have a background in education that makes most american educated PHD's I know look like 6th grade dropouts. but they cant get a job using their knowledge because "you were not educated in the USA".....

So they end up night watchmen, Grocery store clerks, or bank tellers. While back in their country they were educated as Doctors, Physicists, and scientists.

Re:Night Watchman? (4, Informative)

DirePickle (796986) | more than 6 years ago | (#22818618)

He's in Israel, not the US, dude. Save your diatribe for another time.

Re:Night Watchman? (0, Offtopic)

smooth wombat (796938) | more than 6 years ago | (#22818888)

Reread what the OP said. He said the guy is Russian, which is correct. He emigrated to Israel where he solved the solution. He will always be Russian no matter where he lives.

Unless you're suggesting that if a person born in Japan came to the U.S. and became a citizen they are somehow no longer japanese.

Re:Night Watchman? (1)

qw(name) (718245) | more than 6 years ago | (#22819018)

Reread what the OP said.
The person to whom you replied never said he was Israeli. He said "He's in Israel."

Re:Night Watchman? (1, Insightful)

Anonymous Coward | more than 6 years ago | (#22819050)

"Unless you're suggesting that if a person born in Japan came to the U.S. and became a citizen they are somehow^H^H^H^H^H^H^H^H legally no longer j^H^H Japanese."

Fixed it for you.

Re:Night Watchman? (0)

Anonymous Coward | more than 6 years ago | (#22819234)

DirePickle said he's in Israel.. not that he's Israeli

Re:Night Watchman? (2, Informative)

BattleApple (956701) | more than 6 years ago | (#22819306)

He emigrated to Israel where he solved the solution.

IANAM, but I believe he solved the problem, not the solution.

Re:Night Watchman? (1)

nebulus4 (799015) | more than 6 years ago | (#22819582)

Avraham Trakhtman is not a typical Russian name and calling his a Russian wouldn't be entirely true. Unless you think there're only Russians who lives in Russia. His is a Russian-Israeli or Israeli-Russian (depending on where yo are). This means that he was a Israeli in Russia and now he is a Russian in Israel. Yes, it is confusing and also somehow funny, bus sadly it's true.

Re:Night Watchman? (1)

ahabswhale (1189519) | more than 6 years ago | (#22820102)

Actually he was probably a Russian Jew. They usually have non-russian sounding names even though they were born and raised there (as were their parents). However, like many Russian Jews, he emigrated to Israel.

Re:Night Watchman? (1)

DavidShor (928926) | more than 6 years ago | (#22818628)

This happened in Israel, not the America.

And in my experience, you mainly see that America-only stuff in the public sector(and even then, not too often). The business world tends to know better.

Re:Night Watchman? (2, Insightful)

Anonymous Coward | more than 6 years ago | (#22818708)

Come on AC, your premise is patently false. I'm at one of the finer educational institutes in the US, and we have people from all over the world who earned their Ph.D.s from all over the world. If you came from one of the highly respected universities throughout the world, and are brilliant, you will get a job. If you have your Ph.D. from the University of Lower Slobobia, of course its going to be difficult. The quality of education in places in Asia, India, and even Russia varies wildly from their best Universities to their worst. To put it into perspective, its kind of like getting your Ph.D. from the least respected institution here. You probably still won't have a job. At least not a good one.

Also, to suggest that the quality of medical education is similar between 2nd and 3rd world countries is utterly ridiculous. Their degree is still good provided they can pass the boards and certifications. Not many do.

Re:Night Watchman? (2, Informative)

Sparks23 (412116) | more than 6 years ago | (#22819798)

Trakhtman is a Russian Jew who immigrated to Israel in 1992 after the breakup of the Soviet Union, and the article says that he had trouble finding work during the influx of refugees. Not because of his background, but because of a sudden unemployment glut. This is why he previously ended up serving as a night watchman, a laborer, a maintenance worker or whatever else he did.

However, the article ALSO says he's been teaching mathematics at Bar Ilan University since 1995; the university is where he solved the problem.

Re:Night Watchman? (2, Informative)

bob.appleyard (1030756) | more than 6 years ago | (#22820018)

I know a Polish biochemist who works as a maid over here in the UK. Makes more doing that than doing biochemistry stuff in Poland, so he's happy for the moment and sending the money back. I imagine this will change in a few years.

Re:Night Watchman? (5, Funny)

Yvanhoe (564877) | more than 6 years ago | (#22818796)

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

Re:Night Watchman? (2, Funny)

rev124 (928697) | more than 6 years ago | (#22819586)

In Soviet Russia computer invents you!

...ugh, that was stupid.

Re:Night Watchman? (2, Funny)

nomadic (141991) | more than 6 years ago | (#22819782)

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

HE'S NOT A WATCHMAN (4, Informative)

mcmonkey (96054) | more than 6 years ago | (#22818824)

If you RTFA (yes, I must be new here) he worked as a night watchman when he first moved to Isreal. He's been working in mathematics for over a decade.

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.

You might as well say the 2002 Nobel prize in economics went to a lieutenant in the army. It's just a minor detail that he was a lieutenant 50 years before winning the prize.

Re:Night Watchman? (3, Interesting)

reset_button (903303) | more than 6 years ago | (#22818956)

According to Wikipedia [wikipedia.org] , he is a mathematician at Bar-Ilan University in Israel. Here is his homepage [biu.ac.il] hosted by the university. Maybe he was a night watchman, but it looks to me like he's a professor now...

Re:Night Watchman? (0)

Anonymous Coward | more than 6 years ago | (#22819822)

"I'm not surprised he's Russian"

Not really, He is in Israel. The nationality listed on his Russian (actually, most likely Soviet) identity papers was Jewish. The Soviet Union, being officially atheistic, regarded Judaism as a nationality rather than a religion. There was a great deal of discrimination against Jews in the Soviet Union. When Communism collapsed to universal approbation, a lot of Jews left as soon as they could.

My mother is a Jew who left the Soviet Union. In the 1990s more than 40 of her cousins emigrated to the US or Israel. Several of them had advanced degrees in the sciences. Mr. Trakhtman could immigrate to Israel because he is Jewish, and therefore has a right of return under Israeli law.

The writeup is misleading (5, Informative)

karl marx is my hero (1222496) | more than 6 years ago | (#22818422)

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.

Re:The writeup is misleading (1, Funny)

Anonymous Coward | more than 6 years ago | (#22818730)

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:The writeup is misleading (1)

peragrin (659227) | more than 6 years ago | (#22819246)

and Albert Einstien worked in a patent office.

Where one works isn't always a sign of ones abilities.

Yeah, yeah, First Post, but... (1, Interesting)

Emor dNilapasi (455542) | more than 6 years ago | (#22818458)

1) Frist Psot!

2) I read the linked-to blurb(s)* and promptly got confused. I'm sure this is indeed some sort of breakthrough, but could some of the more mathematically-literate Slashdotters out there translate this into an explanation that the rest of us could understand? I'd particularly like to see exactly how this finding applies to real-world applications. Thanks in advance...

* - Why yes, I am new here - how did you know?

Re:Yeah, yeah, First Post, but... (2, Informative)

darthflo (1095225) | more than 6 years ago | (#22818584)

I wouldn't consider myself mathematically literate, but applying the findings of Trakhtman to navigation instructions in the real world would, if I understand the theorem [wikipedia.org] correctly, make finding any point anywhere as easy as "at intersections, follow the pattern red-blue-blue".
What I don't quite get, is the efficiency of this. The WP example looks like, transferred to the real world, a trip from Ohio to Cleveland may very well go through Indiana and Pittsburgh. Not what I'd consider efficient/fast routing.

Re:Yeah, yeah, First Post, but... (3, Funny)

notgm (1069012) | more than 6 years ago | (#22818644)

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:Yeah, yeah, First Post, but... (1)

alcmaeon (684971) | more than 6 years ago | (#22818764)

True, you will never end up in Pittsburgh unless you finally tire of traveling, but you may pass through Pittsburgh many times on your way to Cleveland. Hell, you might pass though Lima, Peru on your way to Cleveland, Ohio. For that matter, you might pass though Cleveland, Ohio itself several times before you complete the trip according to the instructions.

Re:Yeah, yeah, First Post, but... (1)

Bloodoflethe (1058166) | more than 6 years ago | (#22818926)

Yes, this is considered a type of logical mapping and his solution is impressive. It took me a bit to slog through that 8 page set of proofs for his theorem. It's been a while since calculus and the related fields of number theory. Props to the man for pulling this off at 63!

Re:Yeah, yeah, First Post, but... (0)

Anonymous Coward | more than 6 years ago | (#22818662)

Is going from Ohio to Cleveland like going from New Jersey to Hoboken?

Re:Yeah, yeah, First Post, but... (1)

Miseph (979059) | more than 6 years ago | (#22819342)

Wait, is Hoboken the giant pit of raw sewage, or is it just the place next to the giant pit of raw sewage. Frankly, I get confused by New jersey... too much raw sewage in pits.

Re:Yeah, yeah, First Post, but... (1, Interesting)

Anonymous Coward | more than 6 years ago | (#22818722)

It probably isn't the best way to get from one point to another... but it *is* useful to go from an unknown starting point to a destination, which is the point of the problem. I could see that having applications - probably not in real-world navigation since we're not actually going to paint all the roads, but in (as the summary notes) internet routing.

Re:Yeah, yeah, First Post, but... (3, Insightful)

gomiam (587421) | more than 6 years ago | (#22818726)

I am not a mathematician either, but I think being able to provide a pattern that allows you to reach any given point in the graph would allow for faster switching at the nodes (once you reach certain speeds switching becomes the bottleneck). The problem isn't concerned with efficiency but reachability, anyway.

Re:Yeah, yeah, First Post, but... (1)

ptelligence (685287) | more than 6 years ago | (#22819864)

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

Re:Yeah, yeah, First Post, but... (1)

Mawbid (3993) | more than 6 years ago | (#22818986)

The Wikipedia article [wikipedia.org] explains the idea very nicely. Not much there about applications though.

Applications? (4, Interesting)

DigiShaman (671371) | more than 6 years ago | (#22818464)

How soon can we see this implemented in my Garman GPS unit or Google Maps?

Re:Applications? (4, Informative)

MightyYar (622222) | more than 6 years ago | (#22819430)

Egads, please no! This only guarantees that you will arrive at a destination from an arbitrary start point. Even if you could somehow use it for Google directions, your route would be crazy. You could start out next door to your destination and it may take you a day-and-a-half of travel to finally wind up there as you tour all over the city. I can see this being interesting to networking, though. A guaranteed route somewhere from any start point sounds pretty cool, even if a bit inefficient.

Re:Applications? (1)

Zakabog (603757) | more than 6 years ago | (#22819500)

I hope never, I don't want to potentially drive through my destination 20 times to get to it. This doesn't create an efficient route, it just creates a guaranteed route. The instructions might be, turn left, turn right, turn left. Now repeat 40 times and you're guaranteed to get to New York from wherever you started.

Re:Applications? (1)

megaditto (982598) | more than 6 years ago | (#22819686)

Never.

The whole point of having a GPS unit is so that you know your starting location.

If the result apply to 3D spaces, I would say it'll probably have some implication for biotech or nanotech assembley as guidance clues for stem cells or nannites. I'd say it's more likely to be nanotech though, since we already have better ways to guide cells.

Classic maze solution (1)

CustomDesigned (250089) | more than 6 years ago | (#22819982)

The classic maze solution treats the maze as a graph of degree-out 2 decision points (left,right). The classic formulation is to keep your hand on the right hand wall. This fails, of course, when you are inside of a loop. However, this theorem says that while the instruction (right) may fail for such mazes, there exists some longer instruction, say (left,right,left) that will exit the maze regardless of starting point. Some classic myths can now be updated. Instead of our hero relying on a ball of string, or a non-looping maze, an insider can provide him/her with a finite length binary string - disguised of course.

Now for some further questions.

  • For the binary string to work, there has to be a consistent way to decompose complex intersections, like say a room with 12 tunnels entering. Does the binary string work regardless of how complex intersections are decomposed? Or does changing the decomposition algorithm change the exit instructions?
  • Is it possible to put an upper bound on how many applications of a solution string are required to exit the maze? This would greatly help our hero in case he has to try several decomposition methods and needs to know whether a given trial worked or not.
  • "Real" mythical mazes have hazards - vertices that virtually guarantee death if entered. Is there a road coloring and instruction string that works from any starting point, *and* never enters a hazardous vertex?
  • The (left,right) coloring is not actually the same as covered by the theorem, since the coloring changes depending on which direction you are coming from. Do instruction strings still exist? I drew a small maze with a loop, so that the string (right) fails, and exhaustively verified that the string (left,right,left) exits the maze from any starting point. So the conjecture seems reasonable.

It's a theorem (3, Insightful)

pikine (771084) | more than 6 years ago | (#22820078)

It's a theorem which states that if a graph is strongly connected and aperiodic, then there exists a road coloring. It was conjectured by Weiss and proven by Trahtman 30 years later, which is what the article is about. A graph that is periodic may still have a road coloring, but that's not the scope of the theorem.

Most roads are strongly connected but periodic (not aperiodic), in the sense that you can drive around a block in 4 segments, and drive around 2 blocks in 6. The period in this case is 2. You can't guarantee a computer network to be aperiodic either. These graphs may still have a road coloring, but the theorem doesn't apply. Therefore, this theorem has little application in practice.

I haven't read the paper, but there are generally two ways to prove the theorem: (1) show a coloring algorithm that makes only the assumptions of strong connectivity and aperiodicity, or (2) show the contraposition, that if there is no road coloring, then it implies either the graph is not strongly connected or there is period. Only (1) is useful in practice because you have a method to generate road coloring and instructions to reach all vertices, but it's harder to verify that (1) is correct. (2) is not very useful because although you have a proof, but you don't end up with an algorithm that generates road coloring.

In practice, algorithms get things done. Proofs are only certificates.

Night Watchman? (1)

MassiveForces (991813) | more than 6 years ago | (#22818472)

In Soviet Russia, the night watches YOU! So he wasn't needed in his current profession back there and had time to excell in math.

The missing link? (0)

Anonymous Coward | more than 6 years ago | (#22818510)

The link to the solution is missing.

Bad timing. (5, Funny)

Rob T Firefly (844560) | more than 6 years ago | (#22818552)

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

Link to the solution (4, Informative)

wiredog (43288) | more than 6 years ago | (#22818554)

Since the one in the write-up is borken. Here [arxiv.org] it is.

wikipedia (5, Informative)

ZiggyM (238243) | more than 6 years ago | (#22818638)

from Wikipedia: In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. http://en.wikipedia.org/wiki/Road_Coloring_Conjecture/ [wikipedia.org]

Re:wikipedia (1)

Markspark (969445) | more than 6 years ago | (#22818788)

this article doesn't exist on wikipedia yet.

Re:wikipedia (0)

ArcherB (796902) | more than 6 years ago | (#22818918)

if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from.
That doesn't sound too hard. Let's say I live in NY... Tell you friend to drive to the equator, north or south you'll get there eventually. The travel East until you reach Africa. No you give directions to NY and your house from the point where Africa and the equator intersect on the west side of the continent.

In other words, all you need to do is start by giving directions to a known location, the equator in my example, and go from there.

(Hey, TFA said make it simple. I just did it a single line with no colors. Maybe I'm missing something.)

Re:wikipedia (5, Informative)

Jasin Natael (14968) | more than 6 years ago | (#22819120)

The problem is more constrained than that. Think about it more like this: You're in a town that's been planned very carefully. At any intersection, the possible roads away from that intersection are labeled with colors. I'll assume three colors, and that each intersection has exactly three roads leading away from it (the number of roads that lead into the intersection doesn't matter).

Your friend tells you that his address is "Red-Blue-Blue". This means that, no matter which intersection you start from, by repeatedly following these directions, you WILL end up at his house.

Re:wikipedia (1)

magicchex (898936) | more than 6 years ago | (#22819144)

Doesn't help if you don't know how to get to the equator from where you're starting. The way this proof works, you have foolproof directions from any location that are the same as from any other location and require no knowledge of where you're starting or going, just the ability to follow the road "colors" or whatnot.

Re:wikipedia (1, Informative)

nherc (530930) | more than 6 years ago | (#22819048)

Oddly Wikipedia directory/article URL listings seem case sensitive and the given one pointing at 'Road_Coloring_Conjecture' does not work, but 'Road_coloring_conjecture' does. The correct Wikipedia link to the Road Coloring Conjecture page is http://en.wikipedia.org/wiki/Road_coloring_conjecture [wikipedia.org] .

Re:wikipedia (1, Informative)

magicchex (898936) | more than 6 years ago | (#22819174)

Actually it is not case sensitive. http://en.wikipedia.org/wiki/Road_coloring_conjecture [wikipedia.org] works just as well as http://en.wikipedia.org/wiki/Road_Coloring_Conjecture [wikipedia.org]

However, leading slashes break the link, so both http://en.wikipedia.org/wiki/Road_coloring_conjecture/ [wikipedia.org] and http://en.wikipedia.org/wiki/Road_Coloring_Conjecture/ [wikipedia.org] do not work.

Re:wikipedia (1)

Ctrl-Z (28806) | more than 6 years ago | (#22819942)

Actually, it is case sensitive, but a redirect page exists from "Road Coloring Conjecture" to "Road coloring conjecture". But, yeah, the slash thing is more pertinent here (although I think you meant trailing slashes, not leading ones).

link to solution (0, Redundant)

sammy baby (14909) | more than 6 years ago | (#22818680)

Link to solution is busted. Find it here [arxiv.org] .

Re:link to solution (1)

pembo13 (770295) | more than 6 years ago | (#22818758)

I'd be curious to see a digitized copy of his notes

A Subquadratic Algorithm for Road Coloring (5, Informative)

Frans Faase (648933) | more than 6 years ago | (#22818694)

Apart from the referenced paper being some months old, the author has an extended paper with an efficient algorithm. See A Subquadratic Algorithm for Road Coloring [arxiv.org] .

Old news? (5, Insightful)

amplt1337 (707922) | more than 6 years ago | (#22818704)

1. Here's wtf the problem even is [wikipedia.org] , for those of us who aren't all up in the "mathematical curiosities" business. Basically the question is, for a specific kind of graph (where you can go from point A to a finite number of points B, C, or D, etc) can you label the possible paths from each point so that, starting from anywhere, you can follow an invariable rule that will get you to a specific destination point. (Check the link, the picture makes much more sense).

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

Re:Old news? (1)

vsage3 (718267) | more than 6 years ago | (#22818786)

The proof was submitted in september. Granted it's still old even when you take into account it was published in December, 3 months is a pretty short amount of time in academia. As an engineer, I am happy to see that not only has this mathematician proved his solution but he also provided us with an algorithm by which his solution can always be had - some might just stop at proving the existence, which makes it worthless in practice.

Re:Old news? (1)

pohl (872) | more than 6 years ago | (#22819206)

I dunno bout that...I think expecting universal, real-time synchronous absorption of news is pretty unrealistic, and is grounds for handing in your own nerd card.

Re:Old news? (1)

amplt1337 (707922) | more than 6 years ago | (#22819356)

3 mos = real-time, synchoronous? Maybe if your news is delivered by IP-over-Caravel...

Re:Old news? (1)

pohl (872) | more than 6 years ago | (#22820142)

Sorry, let me translate it into non-nerd-speak for you: Your suggestion that this news is too old to be worthy of being published here implies that we all ("universal") should have read ("absorption") this news at the same time ("synchronous") months ago ("real-time") -- when, presumably, you did -- is unrealistic and naïve.

Re:Old news? (2, Funny)

huckamania (533052) | more than 6 years ago | (#22819662)

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:Old news? (1)

Reason58 (775044) | more than 6 years ago | (#22819692)

From the description and picture listed on Wikipedia it seems to me that this method is only possible if every single road is a one-way street. This is hardly a realistic situation except in downtown parts of the largest cities.

Re:Old news? (2, Insightful)

calebt3 (1098475) | more than 6 years ago | (#22819768)

No, just consider every two-way street parallel one-way streets. Each half has it's own color.

Re:Old news? (2, Funny)

Reason58 (775044) | more than 6 years ago | (#22819836)

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:Old news? (1)

calebt3 (1098475) | more than 6 years ago | (#22820034)

R on Lincoln L on 1st St L on R Ave R on Prescott
This method requires you to be at Lincoln headed towards 1st St. The second method doesn't care where you are, just turn onto the nearest orange and go from there. Considering that there are usually only 4 outbound routes from a given intersection, there will only really be a need for 4 colors (at least to get the job done, not that it would be very efficient). Anyways, it has been stated that this is something more useful for network routing that actual use on roads.

Re:Old news? (1)

sconeu (64226) | more than 6 years ago | (#22820052)

From the "what-have-they-ever-done-for-us" department:

In other words, the Romans were right, and "All roads lead to Rome"?

Actually (2, Interesting)

The MAZZTer (911996) | more than 6 years ago | (#22818752)

He did it in 6.5 pages, the rest is references, whitespace at the very end, and the abstract and title.

Re:Actually (1)

The MAZZTer (911996) | more than 6 years ago | (#22818766)

Err, I mean 5.5 pages.

Re:Actually (1)

qw(name) (718245) | more than 6 years ago | (#22818964)

The proof takes up 5.5 pages all typed up and pretty. His original proof was hand-written and consumed 8 pages.

Re:Actually (4, Funny)

spookymonster (238226) | more than 6 years ago | (#22818794)

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?

Sign of a true Genius. (4, Insightful)

Lumpy (12016) | more than 6 years ago | (#22818756)

"Some people think they need to be complicated. I think they need to be nice and simple."

The man is a True Genius. Insight to all of out out there, that is the proper way of thinking.

Re:Sign of a true Genius. (0)

Anonymous Coward | more than 6 years ago | (#22819756)

"For every problem, there is a solution that is simple, elegant, and wrong." - H.L. Mencken

Re:Sign of a true Genius. (4, Funny)

Jamil Karim (931849) | more than 6 years ago | (#22820166)

The man is a True Genius.
Real Men of Genius!
Today, we salute you, Mr. former-nightwatchman-turned-mathmetician!

OK, but... (1)

BenSchuarmer (922752) | more than 6 years ago | (#22818854)

How many paths must a man walk down before you can call him a man?

Re:OK, but... (4, Funny)

KDR_11k (778916) | more than 6 years ago | (#22819098)

Forty-two.

Re:OK, but... (1)

ScrewMaster (602015) | more than 6 years ago | (#22819104)

How many paths must a man walk down before you can call him a man?

Well, unfortunately for all us Free Worlders out there, that path is apparently a Red one.

Re:OK, but... (0)

Anonymous Coward | more than 6 years ago | (#22819232)

I think it's just the one, "The Path To Beer".

Unfortunately now I'm too pissed to care anymore.

HIRED! (2, Funny)

TheGreatOrangePeel (618581) | more than 6 years ago | (#22818856)

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

Re:HIRED! (0)

Anonymous Coward | more than 6 years ago | (#22819906)

in fact it's good to learn russian if you want to work for google anyway, because sergey brinn, one of google co-founders is russian

Slashdottings in real life? (1)

tepples (727027) | more than 6 years ago | (#22818878)

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.
If a thousand people arrive at a shopping mall, at the same time, isn't that called a flash mob [wikipedia.org] ? Then I guess this conjecture has already been solved online, and it is called Slashdot.

Re:Slashdottings in real life? (1)

calebt3 (1098475) | more than 6 years ago | (#22819594)

A Slashmob!

Re:Slashdottings in real life? (1)

The_mad_linguist (1019680) | more than 6 years ago | (#22819868)

If a thousand people arrive at a shopping mall, at the same time, isn't that called a flash mob?
I'd call it business as usual.

there are a lot of roads (0)

Anonymous Coward | more than 6 years ago | (#22819032)

to get to my place just take red, blue, orange, green, purple, indigo, neon green, yellow, beige, magenta, black, teal...

What about the cyclical traps? (1)

Muad'Dave (255648) | more than 6 years ago | (#22819080)

Given this graph [wikipedia.org] , what about the 'traps' that exist for directions 'rrr' and 'bbb'? If you number the nodes top to bottom, left to right as 1-8, nodes 1, 2, and 4 all are destinations for 'rrr' depending on your starting point. Similarly, nodes 6, 7, and 8 are all destinations for 'bbb' depending on where you start. Does the problem definition say you must follow the whole direction, i.e. you must always traverse 3 arcs, or is it 'legal' to stop when you've reached your destination (assuming you know where that is). If the latter is true, then the correct destination for 'rrr' is node 2, and node 6 for 'bbb'.

Dir Dest
--- ----
bbb 6*, 7, 8
bbr 3
brb 1
brr 4
rbb 7
rbr 5
rrb 8
rrr 1, 2*, 4

*true node given the 'stop early' conjecture, above.

Re:What about the cyclical traps? (1)

OeLeWaPpErKe (412765) | more than 6 years ago | (#22819280)

The solution is rbb rbb rbb (just try it, pick a starting node, no matter which, and follow the outgoing red arc, then twice the blue one, repeat three times).

It seems to work.

Re:What about the cyclical traps? (1)

Muad'Dave (255648) | more than 6 years ago | (#22820280)

I agree that specific solution works, but what about the general cases of the other 3 length permutations of 'r' and 'b'. As my table shows, all the nodes have unique, universal directions to them except nodes 1, 4, 7, and 8. These nodes have monocolor loops point to them. Try 'bbb' and 'rrr' from any node, and you'll find 3 terminal nodes for each path.

Washington - RNC ??? (2, Funny)

zappepcs (820751) | more than 6 years ago | (#22819178)

"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:Washington - RNC ??? (1)

Stanistani (808333) | more than 6 years ago | (#22819340)

I have derived an interesting algorithm to achieve this; unfortunately, this post is too small to contain it, and it involves an infinite number of monkeys trained to use word processors.

Re:Washington - RNC ??? (1)

idlemind (760102) | more than 6 years ago | (#22819866)

OH NO YOU DIDN'

Here's an example... (0)

Anonymous Coward | more than 6 years ago | (#22819202)

http://en.wikipedia.org/wiki/Road_coloring_conjecture [wikipedia.org]
Wikipedia has a relatively clear example of the problem

Slashdot Mathematical Challenge: (-1, Troll)

Anonymous Coward | more than 6 years ago | (#22819720)


Find a way to send this WAR CRIMINAL [whitehouse.org] to jail.

Post the results at Slashdot and become famous.

 

so.. (1, Funny)

g0dsp33d (849253) | more than 6 years ago | (#22819784)

That means my screensaver could be an Internet network diagram?

What is road-coloring (and why we should care) (4, Interesting)

kevinatilusa (620125) | more than 6 years ago | (#22820004)

The question behind road coloring is this: Given a directed network with out-degree 2 (from any place you can get to exactly two other places), we want to color the edges leading out of each node red or blue so the following "universal directions" condition exists: For any final destination A, there is a set of directions (e.g. take red three times, then blue twice, then red again) that gets you to A no matter where you started from. It may not be the shortest path, but you'll get there. There is one obvious obstruction and one slightly less obvious obstruction: If your network is disconnected so you can't get to A from your starting point no matter what path you follow, you're clearly stuck. On the other hand, there's also a "periodicity" obstruction if all of the cycles of the graph are multiples of the same number. For example, suppose that you were trying to give universal directions for a square, where the roads in question connected every vertex to its two neighbors. If I want to go from my starting point to an adjacent vertex, I have to take an odd number of steps. If I want to go from my starting point to the opposite vertex, I have to take an even number of steps. This means I can't even know how many steps I have to take (let along which steps) unless I knew where I started. It was conjectured, and Trahtman showed, that these two are the only possible obstructions. In particular, he even gives an algorithm for figuring out how to label the roads quickly. I guess the applications I'd see in this are for algorithms and the design of autonomous systems. The idea here is that, if the robot gets stuck somewhere in a multi-step procedure, you may want it to restart from the beginning. However, this can be difficult if the robot does not know where it is in the procedure, or even where it is physically. Trahtman's algorithm could allow you to exchange some computation at the beginning of the procedure (which can be done before the robot goes out, for example), for this "reset" functionality. I don't know whether this is feasible or not though.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>