Puzzle – shortest road system

Let’s say you’re contracted to build roads to connect four towns that are at the corners of an imaginary square with sides 1 mile. What’s the shortest length of road system you can build so that every town can get to every other town?

The first answers that come to mind for most folks are either to do a perimeter road with one one side left off which is 3 miles or to build roads in the shape of an X – which pythagoras tells is would be 2 * sqrt(2) = 2.828 miles.

We can do better. Click on this link to see what the road system would look like, and the theory behind it.

To work out the total length we can use some basic calculus:

Call x the length of shared highway in the middle. So the total length of the road will be:

l\;=\;4\sqrt{(\frac{1}{2})^2 + (\frac{(1-x)}{2})^2}\;+\;x

Simplifying:

l\;=\;\sqrt{4 + 4(1-x)^2}\;+\;x

We’re trying to find x where l is the shortest. So we can differentiate l with respect to x, and set this equal to zero. Recall the chaining rule from high school?

\frac{dl}{dx}\;=\;\frac{1}{2}\;*\;(4 + 4(1-x)^2)^{-\frac{1}{2}}\;*\;8(1-x)\;*\;-1\;+\;1\;=\;0

\frac{1}{\sqrt{4 + 4(1-x)^2}}\;=\;\frac{1}{4(1-x)}

4 + 4(1-x)^2\;=\;\frac{1}{16(1-x)^2}

12(1-x)^2\;=\;4

1-x\;=\;\sqrt{\frac{1}{3}}

x\;=\;1-\sqrt{\frac{1}{3}}

And now we can substitute to find the total length of the road:

l\;=\;4 * \sqrt{\frac{1}{4} + \frac{1}{12}}\;+\;1\;-\;\sqrt{\frac{1}{3}}

l\;=\;4 * \sqrt{\frac{1}{3}}\;+\;1\;-\;\sqrt{\frac{1}{3}}

l\;=\;3 * \sqrt{\frac{1}{3}}\;+\;1

l\;=\;sqrt{3}\;+\;1

This works out to be 2.732 miles, a little better than our original X approach.

It’s neat that the angles turn out to be 120 degrees (as is shown in the link above). A colleague declared to me that this was ‘obvious’, but it’s not so obvious to me. Can anyone find a trigonometric way to solve this problem that doesn’t involve the calculus? Or at least provide an explanation for why the 120 degrees makes sense (other than that it’s a beautiful symmetry)?

Now, only because I’m a maniac and am weirdly enjoying doing high school Calculus for the first time in a while, I’m going to do this again this time picking x to be the distance from the shared highway to the edge of the square. So the shared highway length will be 1-2x.

l\;=\;4\sqrt{\frac{1}{4} + x^2}\;+\;1\;-\;2x

Simplifying:

l\;=\;\sqrt{4 + 16x^2}\;+\;1\;-\;2x

Now we differentiate:

\frac{dl}{dx}\;=\;\frac{1}{2}\;*\;(4 + 16x^2)^{-\frac{1}{2}}\;*\;32x\;=\;2

\sqrt{4 + 16x^2}\;=\;\frac{1}{8x}

4+16x^2\;=\;64x^2

4\;=\;48x^2

x\;=\;sqrt{\frac{1}{12}}

Now we can substitute for the length:

l\;=\;4 * \sqrt{\frac{1}{4} + \frac{1}{12}}\;+\;1\;-\;\sqrt{\frac{1}{3}}

Which we can see is identical to what we had above, so our length is again:

l\;=\;sqrt{3}\;+\;1