This Riddler problem is about efficient road-building!
Consider four towns arranged to form the corners of a square, where each side is 10 miles long. You own a road-building company. The state has offered you \$28 million to construct a road system linking all four towns in some way, and it costs you \$1 million to build one mile of road. Can you turn a profit if you take the job?
Extra credit: How does your business calculus change if there were five towns arranged as a pentagon? Six as a hexagon? Etc.?
Here is a longer explanation:
[Show Solution]
This is actually a famous combinatorial optimization problem with a long history. So rather than attempt to re-invent the wheel, I’ll summarize what is known about the problem and give some pointers to the relevant literature. The problem is known as the Steiner tree problem and shows up, for example, in circuit design. The problem of connecting components on a circuit board using as little wire as possible is precisely the Steiner problem!
In the graph version of the Steiner problem, you have a graph with edge weights (think of the weights as distances) and some of the nodes are labeled as “terminals”. The goal is to find a set of edges that connect all the terminals together. Not all nodes need to be part of the path. This is similar to the minimum spanning tree problem (if all nodes are terminals) or the shortest path problem (if there are only two terminals). Although these simpler variants have polynomial-time algorithms (they’re efficiently solvable), the graph version of the Steiner problem is NP-Hard. So there is likely no efficient algorithm for solving it in general. One thing we know for sure is that the optimal solution should not contain any cycles, because removing an edge from the cycle still connects the same nodes yet has a shorter path. In other words, the solution will always be a tree. This is why it’s called the “Steiner tree problem”.
If we consider the general (non-graph) version of the problem, the solution will still be a tree. A key insight is that we may need to add extra nodes to help make the path shorter. These extra nodes are called Steiner points. For example, consider the equilateral triangle case:
In this case, the version on the left has the shorter path. So we benefit from adding a Steiner point. For an arbitrary triangle, this point is called the Fermat point. The problem gets progressively more difficult as we add more terminal points. The solution for a square involves adding two Steiner points:
Some things are known about more general geometries. The following results, which I will summarize in bullet points, come from a paper from 1930 by Vojtěch Jarník. The paper is open-access so feel free to take a (free) look!
- The optimal solution is a tree whose nodes are a combination of the original nodes of the problem as well as some number of Steiner points.
- If $S_n$ is the number of Steiner points for the problem with $n$ points, then $0 \le S_n \le n-2$. The actual value of $S_n$ will depend on the particular arrangement of the points.
- Every Steiner point has a degree of exactly three. So every Steiner point we add has exactly three roads connecting to it.
- The roads that connect to each Steiner point do so at angles of 120 degrees.
The proofs of the last two facts uses contradiction. For example, we might assume that there exists a Steiner point with three roads at angles that are not 120 degrees, and then we show that it’s possible to move that Steiner point slightly and make the total sum of the roads shorter. Therefore, we conclude that the original geometry could not have been optimal.
These facts alone aren’t enough to tell us exactly what the solutions will be, but it can help us narrow down the search! Also, it’s a quick sanity check to see whether a proposed solution can be improved in an obvious way.
Here is the solution with minimal explanation:
[Show Solution]
For an equilateral triangle, a square, and regular pentagon, the solutions have 1, 2, and 3 Steiner points, respectively. Here is what they look like:
Note that these solutions satisfy the requirements listed in the text above. Namely, each Steiner point (internal node we added) has exactly three edges emanating from it and they form angles of 120 degrees with one another. When we have a regular polygon with more than 5 sides, there are no Steiner points and the shortest road is simply the one that traverses the perimeter and leaves out one edge. For example:
This fact is proven in the following 1987 paper by Du, Hwang, and Weng.
Of course, if the polygons are not regular, all bets are off! Depending on how the points are arranged, we could have a different number of Steiner points and finding the optimal arrangement is generally very challenging.
The minimal road length for a regular polygon with sidelength $r$ is:
- $3$ sides: $\sqrt{3} r \approx 1.732r$.
- $4$ sides: $(1+\sqrt{3})\,r \approx 2.732r$.
- $5$ sides: $\frac{1}{2} \sqrt{7 \sqrt{5}+\sqrt{174 \sqrt{5}+390}+17}\, r \approx 3.891r$
- $n\ge 6$ sides: $(n-1)r$.
In the original problem statement, $n=4$ cities and $r=10$ miles. So we require 27.32 miles of road, which will cost less than \$28M to build. Therefore we do turn a profit (of about \$680k) by accepting the job.
It’s worth mentioning that this problem can also be solved with soap! Here is a neat video that explains and demonstrates it.