(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.
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:
- 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.
- 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.)
