29
$\begingroup$

(This problem is from the 2024 Konhauser Problemfest, written by Stan Wagon.)

Eleven cities, one of them being Rome, are arranged in a circle, with adjacent cities joined by a pair of one-way roads, as shown in the diagram below.

A diagram of the eleven cities

Your task is to give the inhabitants of these cities clear and simple instructions for how to get to Rome. When I say simple, I mean very simple. If the first step of the instructions is to look around and check which city you're currently in, that's already too complicated.

Instead, you must do the following:

  1. Paint each of the 22 roads (the arrows in the diagram) red and blue. Each city must have one red road and one blue road leading out of it.
  2. Write down a sequence of colors (such as "red, red, red, blue, blue, red, blue, red, blue, red") that will serve as directions to Rome. Starting from any city, following the roads of these colors should lead to Rome after following the last instruction.

(Bonus: find a solution in which the directions have as few steps as possible.)

Improve this question
$\endgroup$

4 Answers 4

Reset to default
20
$\begingroup$

This should work.

  1. The colouring:

edge-coloruing

  1. The sequence:

5 R's followed by 5 B's.

Bonus:

Label the cities 0, …, 10 starting from Rome and going in anticlockwise direction. Then, starting from city i, the number of clockwise steps (ci) must be i more than the number of anticlockwise steps (ai) modulo 11, i.e., ci - ai = i mod 11. But we also want the total number of steps to be the same starting from any city. In particular, c0 + a0 = c1 + a1. If c0 ≠ a0, then we already need at least 11 steps, so we must have c0 = a0. Then, c1 + a1 must be even, which means c1 - a1 = 11k+1, where k is odd. It follows that c1 + a1 ��� |11k+1| ≥ 10 since k is odd. Therefore, the above solution is minimal.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ To anyone wondering how I came up with this colouring, I tried doing this for 3 cities, then 5 cities, and noticed that reveal spoilerfor n = 2k+1 cities, k+1 R's followed by k B's always seemed to work, and when you start from Rome, you go all the way around. This fixes all the colours of the edges. $\endgroup$ Commented 2 days ago
  • 1
    $\begingroup$ I have improved the answer since I posted the above comment. Instead of reveal spoilerk+1 R’s, we need only k R’s. $\endgroup$ Commented 2 days ago
  • 1
    $\begingroup$ Correct - well done! $\endgroup$ Commented yesterday
  • 3
    $\begingroup$ Nice, I wondered how to prove it was minimal. To rephrase the proof: Rome itself must use an out-and-back route, or else go all the way around and use more than 10 steps. Any out-and-back route consists of an even number of steps, therefore the optimal plan has an even number of steps. But the only way to use an even number of steps starting from only 1 step away is to go 10 steps around the other way - we can't do better than 10 steps. $\endgroup$ Commented yesterday
  • $\begingroup$ @NuclearHoagie. Exactly, I need not have used so many symbols but that's essentially the argument. $\endgroup$ Commented yesterday
10
$\begingroup$

A different answer:

enter image description here

The strategy:

Take a red road, then a blue road. Repeat four more times.

The explanation:

Starting at Rome and moving clockwise, number the cities 0, 10, 2, 8, 4, 6, 6, 4, 8, 2, 10. Taking a red road, followed by a blue road, takes you from 0 to itself, and from any other number N to N-2. This means that Rome is N cities away, and 10 roads are sufficient to lead to Rome.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Also correct! I don't know whether there are any solutions other than the two found so far. $\endgroup$ Commented yesterday
  • $\begingroup$ @MishaLavrov. Are there official solutions? Which solution do they give? $\endgroup$ Commented yesterday
  • 2
    $\begingroup$ @Pranay The official solutions are here and they give both approaches (as well as an interesting argument for why there is no shorter set of directions). $\endgroup$ Commented yesterday
  • $\begingroup$ @MishaLavrov. Oh wow, that’s much simpler than the argument in my answer and very clear. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @Pranay I was only counting optimal solutions. I'll write up an answer in a few hours. $\endgroup$ Commented yesterday
7
$\begingroup$

Here is a way to find the right coloring of the roads.

First:

Note the distance of each city from Rome, mod 2. I've marked them below:

Distances from Rome, mod 2

More importantly, for most neighbors, their values are different. However, for the two cities furthest from Rome (circled), they are neighbors, and their values are both 1. Call these the critical points.

These are critical, because:

For our set list of instructions, we start at some variable distance from Rome, mod 2. We need to end at a set distance from Rome, mod 2.

This implies the strategy is to:

Repeatedly move towards a critical point/between critical points until all starting positions end up on one of these. Then, just take 5 steps towards Rome to complete the trip.

The strategy can be executed as follows:

Color all roads towards the critical points, as well as between them, in one color, say red. This fixes all road colors. There is one anomaly - Rome itself cannot have two outgoing red roads, so just arbitrarily color one of these blue. All remaining roads (towards Rome) are colored blue.

Then, take the red road five times. Note that this executes the first step of the strategy - all red roads lead to a critical point. The longest it takes for a traveler to end up at a critical point is five steps (from Rome itself).

Then,

Just repeat the opposite instruction (blue in this example) five times, and we are done.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Correct! I like the explanation of how you found the solution :) $\endgroup$ Commented yesterday
5
$\begingroup$

Here is a general solution. Yeah, there are more than two.

Each city can be said oriented clockwise or counter-clockwise in the sense of which way the blue road goes.

The simple rule is that the cities must be oriented symmetrically relative to Rome. If the city n steps clockwise of Rome is oriented clockwise, then the city n steps counter-clockwise from Rome must be oriented counter-clockwise. And vice-versa.
The path to write down is just whatever it takes to go from the city just left or right of Rome, around the circle, back to Rome.

This give 64 solutions with a path of length 10. You can choose the correlated orientation of the 5 pairs of cities and the orientation of Rome.

It works because ...

Imagine two police cars starting from Rome's two neighbor cities, going around the circle and back to Rome, one clockwise, the other counter-clockwise. They follow the prescribed path.

A car C starting from any other cities at the same time would move randomly at first, following a path for cities it wasn't meant for.
But sooner or later C will meet one of the police cars. And when that happens it will be in the right city at the right time for the path, which means it will then follow the path with the police car down to to Rome.

Depending on the parity of the starting position, one of the police cars will catch the car. If the car tries to escape it and pass Rome before the police car reaches it, it won't help because it will then run into the other police car arriving in the other direction. So, whatever the car does, it will bump into a police car and be directed to Rome.

How general is it?

These are indeed the only solutions for a minimal path length.

It has been shown that the minimum path length is 10. It means a car starting left or right of Rome must go straight around the circle, without changing direction. Since for both a clockwise and a counter-clockwise round trip the instructions are the same, the orientation of the cities must be symmetrical about Rome. And the round trip determines the driving instructions uniquely.
So this condition of symmetry is necessary and we have seen it is also sufficient.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Nice! After thinking about your proof that this works, I thought of a different formulation of it. reveal spoilerPut a car in each city, and think of this as being in positions -10, -8, -6, ..., 8, 10 relative to Rome, where positive is clockwise and negative is counterclockwise. As the cars move, adjust their positions up or down by 1. Since all cars have the same parity, two cars can't switch signed positions without meeting, and once they meet, they're stuck together. So if car -10 and 10 both meet at 0, every car which was between them must be at 0 as well. $\endgroup$ Commented yesterday
  • $\begingroup$ @MishaLavrov yes, it makes the clearer that that police cars will indeed collect all cars. $\endgroup$ Commented 22 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.