IBM Research | Ponder This | July 2003 challenges
Skip to main content

Ponder This

July 2003

<<June July August>>


Ponder This Challenge:

This is an old problem due to Roy Adler, Wayne Goodwyn and Benjamin Weiss. To our knowledge, it remains unsolved.

We are given a collection of N cities and 2N one-way roads. (For example, we are told that the two roads leading out of Pittsburgh lead to Buffalo and Erie, respectively.) Each road leads from one city to another (or possibly back to the same city). Each city has exactly two roads leading out of it, and at least one leading in. We are assured that it is possible to proceed from any city to any other city by legal moves along the roads (that is, in the proper direction).

We must impose one other technical condition:
Define a "cycle" to be a route leading from one city through some other cities and back to the starting point (following the roads legally, and without visiting any city twice), and the "length" of a cycle to be the number of roads traversed. We must assume that for each prime number p there is a cycle whose length is not divisible by p. (For example, not all cycles have length divisible by 3.)

Our task is to color each road red or green, so that for each city the two roads exiting that city have different colors, and so that "universal directions" can be given: namely, if a friend calls up and says "I don't know where I am; how do I get to Pittsburgh?", we can respond: "Take the red road out of your present city, then the green road, then the next green road, then red, then green, and then red; then you will be in Pittsburgh."

Notes:
It is not enough to guarantee that these universal directions lead our friend THROUGH Pittsburgh somewhere along the line; she must END UP in Pittsburgh.

The problem: Show that (under the given assumptions) we can always color the roads so that the "universal directions" can be given. Or, give an instance (satisfying the given assumptions) for which there is no such coloring.

Example: Suppose we are given three cities A,B,C, and we are given roads (AB), (AC), (BA), (BB), (CB), (CC).
(The first is a road from A to B; etc).
We decide to color roads (AC), (BB), (CB) green, and color (AB), (BA), (CC) red.
Now when someone calls up and asks to get to B, we tell him to take two green roads.
If he asks to get to another city, say C, we first direct him to B and then from B to C; so we tell him "Green Green Red Green".
You can check for yourself that no matter where he starts, these directions get him to C.


We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

  

Challenge: 07/03/03 @ 01:00 PM ET
Solution: 07/31/03 @ 01:00 PM ET
List Updated: 07/03/03 @ 01:00 PM ET

People who answered correctly:


Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.