Bagel Math

The Three Utility Problem is a classical mathematical puzzle:

Three customers, Alice, Bob, and Charlie, all want to connect their houses to three different utilities, Electricity, Gas, and Water. Can each customer run a line to each utility company in such a way that the lines don’t cross?

The easiest attempt – just drawing all the lines in straight – doesn’t work. It makes several crossings.

Even if we try to reroute some of the lines, it seems impossible to eliminate every crossing.

We don’t have to play with the problem too long before we start suspecting it might be impossible. And indeed it is. To convince ourselves that this problem can’t be solved, think about what a solution would have to look like. Among other features, it would have to contain the cycle of lines $AE$, $EB$, $BG$, $GC$, $CW$, and $WA$, and none of those lines cross. The remaining lines ($AG$, $BW$, and $CE$) each join opposite locations along the cycle, in the sense that the positions are each $3$ away from each other and the entire cycle consists of $6$ locations.

So, we might draw one of those lines inside the cycle (highlighted in gray below), but when we do, we cut the inside of the cycle in half, and neither of the $2$ remaining lines can fit in the inside with it. For example, if $BW$ is drawn on the inside, then $A$ and $G$ are cut off within the inside, as are $C$ and $E$. So, at most one line can be drawn on the inside of the cycle.

Similarly, we can draw one line on the outside of the cycle, but no more. There are $6$ lines in the cycle itself, so counting the inside and outside, we can draw a total of $6+1+1=8$ lines, but the problem requires $3\times 3=9$. The problem is impossible.

At least, the problem is impossible on Earth. It could be possible if Alice, Bob, and Charlie were living on a planet shaped like a torus (a mathematical donut shape). The diagram below shows how: the black lines get drawn in straight, the purple one wraps around the outside rim of the torus, the blue ones wrap around the inside of the torus’s hole, and the orange line wraps both ways.

None of these lines cross, but it’s not at all obvious at first glance why not. The orange and purple lines in particular seem suspicious: looking at the right side of the diagram, the orange line starts above the purple one, but by the time they end up at $A$ and $E$, their positions have reversed. How can they not cross in between? As it turns out, they don’t, but instead of taking my word for it, you might just want to get out a bagel for practice.