Four towns are located at the vertices of a 4 mile by 6
mile rectangle. By using three sides of the rectangle, a road
network of total length 14 miles can be constructed which connects
all four towns. Is there a shorter road network, which connects the
towns? Specifically, there is a suitable network of length less
that 13 miles.
Hint 2
Add two new points inside the rectangle, and
find a network with roads branching off at those two points.
Hint 3
Fix a point on the segment parallel to the long side of the
rectangle, passing through the center, and at distance t
from one of the short sides. Then draw segments from each vertex
on that same short side to that point. Repeat the same on the other
short side, and join the two paths. Now calculate the total distance
as a function of t, and use Calculus to find the minimum of
this function.
Click here for rest of the solution.
The Rest of the Solution
The picture below shows the road network.
The total distance
is f(t) = 4\sqrt{4+t^2} + 6 - 2t.
Taking the derivative and setting it equal to zero, we obtain
the equation
\frac{4t}{\sqrt{4 + t^2}} - 2 = 0,
whose only positive solution is
t = 2/\sqrt{3}.
This is a minimum for f(t),
and
f(2/\sqrt{3}) = 6 + 4\sqrt{3} \approx 12.93
is the length of the corresponding road network.
Notes
by Allen Stenger
The generalization of this problem to
n
towns, arbitrarily
placed in the plane, is called the Steiner problem, after
Jakob Steiner, a 19th century geometer. The Steiner problem
is the subject of a great deal of research today, both for
its practical applications and for its purely mathematical
interest. The applications include physical design of
integrated circuits, message routing, design of switching
networks, and the phylogeny problem in computational biology.
It turns out that, if we don't allow any additional points,
it is easy (even for a large value of
n)
to compute the minimum
distance needed to connect
n
towns; this is called the
"minimum spanning tree" problem. But for the Steiner problem,
where we allow added points, the amount of computation needed
grows very rapidly with
n,
so that even with computers it quickly
becomes impractical. Therefore there is great interest in finding
good
approximate solutions to the Steiner problem, and in estimating
how good they are (usually in comparison to the minimum spanning
tree).
References
-
Richard Courant and Herbert Robbins, What is Mathematics?,
2nd edition, Oxford University Press, 1996. "Recent Developments", section 10,
"Steiner's Problem" (pp. 507-513) gives recent developments in this area.
-
You can read Josh's original question here.
-
Wikipedia has an article on the
Steiner Tree Problem.
