Mountain Cheng

Roundabouts are great if you don’t like waiting for traffic lights; the downside is that there tend to be more accidents. We can describe this more precisely with a “danger number”: given a car journey, its danger number is the number of places where the car must merge with oncoming traffic. For example, in the diagram below, the danger number would be 2 for the blue car, since it enters road 1 and drives past road 2. Note that it does not merge at road 3. Similarly, the red car doing a U-turn has a danger number of 5.

To simplify, assume that all roads are two-way, meaning that each road joined to a roundabout is both an entrance and an exit. Also assume that roads may not pass over each other. 

Here’s the puzzle: can you design an intersection for 12 roads using roundabouts, so that the danger number of any car journey is at most 9?

Notice that a big roundabout with all 12 roads joined to it is not good enough because, for example, a  journey from any road to the next road counterclockwise from it has a danger number of 11, which would be greater than 9. 

So, what can you do? One idea is to have two mini roundabouts, each receiving 6 roads in addition to a  road linking the two roundabouts (see diagram below). In this design, a U-turn only has danger number 7. However, there are other journeys with danger number 12. We have to be more strategic.

[Scroll down bit-by-bit to see the solution] 

. 

. 

. 

.

.

.

.

.

.

.

There are multiple solutions. One idea is to make a ring of roundabouts: it doesn’t work with 3 but it does with 4. I’ve drawn an example of the most dangerous journey possible on this design. 

Here is another idea: use one roundabout as a sort of “centre” surrounded by four outer roundabouts. Each of the outer roundabouts receives 3 roads plus one road connecting to the “centre”. You can check that the danger number is at most 9.

Similarly, we can use 6 outer roundabouts:

This even works with 5 outer roundabouts, with the outer roundabouts receiving 3, 3, 2, 2, 2 roads  respectively. 

Now that we’ve found a solution, two natural follow-up questions come to mind: is this the best solution, in other words, is there a design that guarantees danger numbers no more than 8? Another question then is, what can we do about the danger numbers if we change the problem, say, to 13 roads, or 24 roads, or other numbers? 

More concisely, the question now is: given N roads (where N is at least 3), what is the smallest upper bound for the maximum danger number? 

For example, we know the answer is at most N, since we can use a single roundabout. For N = 12 we  know the answer is at most 9, but it could be lower. 

Here I’d like to show you a neat trick: consider e.g. N = 48 = 4*12. Then we can construct a design for N = 48 as follows: take a roundabout with twelve exits and attach to each exit the solution for N = 4, which is a roundabout receiving 4 roads. Then on this diagram, the most dangerous path will traverse exactly two mini roundabouts of size 4, and the centre roundabout with size 12, so (with careful counting) this design has a maximum danger number of 2*4 + (12 – 1) = 19. This is already quite a big improvement over the single roundabout solution with danger number 48.

In general, given a factorisation N = a*b, we can construct a design for N by attaching a copies of the  design for N = b around a roundabout of size a, as drawn below (crudely). 

Using this method, we can get some pretty wacky pictures, for example this design for N = 3*5*6 = 90:

For the purposes of this problem, we can do EVEN better: we can also modify the “centre” by substituting a known solution for N = a. This becomes a little harder to visualise, but I hope you trust me that this design will have a danger number of 2*D(b) + (D(a) – 1). Applying this improvement to our  N = 48 = 4*12 case, we get two bounds: if we set a = 4 and b = 12, this gives 2*9 + (4 – 1) = 21, while a = 12, b = 4  gives 2*4 + (9 – 1) = 16.

Unfortunately, I do not actually know if 9 is the least upper bound for N = 12; I’ll leave that as a puzzle for you. I’d like to instead point out that this trick to build designs is an example of the problem-solving principle of reduction – solving a complicated problem by subdividing it into smaller, easier pieces. Indeed, this is one of the finest tools used by mathematicians. 

PS. You might have thought to insert a road “inside” a roundabout, hoping it acts as a shortcut that  shortens journeys. Unfortunately, this is equivalent to using two mini roundabouts to start with. (Do you see why?) It is therefore pointless to subdivide a roundabout. 

PPS. In case you’re curious, there is a rather famous roundabout with 12 roads: the Place Charles de  Gaulle located in Paris.