Wednesday, March 26, 2008

Wednesday Math, Vol. 18: The Road Coloring Problem

So here's the deal. You have a closed system of locations and one way-streets leading from location to location. If you pick any two locations, there exists a series of roads leading from one place to the other and vice versa. For every location, there are the same number of roads leading out, and that number is at least two. There's also a rule about the length of round trips, that they can't all be divided by some number bigger than one. This would make the synchronization we seek impossible.

Since every location in the picture above has two roads leading out, and since I am a good leftist and all, I paint the choices red and black. It's the painting choice that matters, because not all of the possible painting choices will allow me to do the thing I can do with this choice. Pretend there is an army of robots (or in math, automata) wandering around this system of locations, known in math as a graph. I can broadcast messages to all of them simultaneously, telling them what color road to take next. If they are spread all over the place, I can send the message black, black, black, red, and no matter where they started, all of them will be at location B when they finish those four moves. Since one of the rules is that there is a path from any location to any other, that means I can send a broadcast that will get all the robots to any location simultaneously, once I have them all in lockstep at location B.

The unsolved problem was if there was a coloring that would have this synchronization process for any graph that met all the stipulations, no matter how big, no matter how many roads leading out all the locations had. The answer is yes, according to a paper published in 2007 by Avraham Trahtman, a Russian mathematician now living in Israel. The problem was first proposed in 1970, by mathematicians other than the solver, and some are making a fuss over the fact that Trahtman is 63 years old, when math is supposed to be a young person's game. In point of fact, though a lot of important math is done by people under the age of 30, there are plenty of instances of people still doing good work all their lives, or having the big breakthrough well past the age of 30.

Kudos, Dr. Trahtman!


pissed off patricia said...

I think I threw my brain out of gear just reading this post. Have mercy on me, it's only about 9:30 in the morning here. At this time of day my IQ matches my age.

Olo said...

What you're looking for is just above B, but only use one finger and go slow the first time.

Matty Boy said...

It's kind of like those math magic tricks where you tell someone to take their age and add 1776 and do a bunch of stuff then presto! It's their mom's maiden name! (This trick not actually possible.)

If you go black, black, black, red from F, you go to A, then E, then back to F, then to B.

If you go black, black, black, red from D, you go to E, then F, then A, then to B.

ken said...

You can actually do it one step quicker, with black, black, red. Actually, my gut says this should be possible in ceiling(log_2 n) steps, though no proof comes to mind.

- ken

Matty Boy said...

Nice catch, Ken. I'd re-write the entry to fix that, but I'd actually have to redraw the picture as well.

All I can say is, oopsie!