A,B,C and D are four cities such that ABCD has the precise shape of a square with each side equal to 100 kilometers.
A railway network needs to be constructed connecting all the cities. Determine the minimum total length of this network. Prove that this is indeed the minimum network length.
From memory I know that the optimal network would have all its nodes such that at each one of them three lines meet at 120° angles. This is usually illustrated with soap bubbles with dihedral angles, and of course the planar solution follows in cross section.
So two cities that are adjacent (share a side of the square), say A and B are connected by a broken line that indents into the square, forming the two equal sides of an isosceles triangle with a vertex angle of 120°. The same is done for C and D. Then a line segment joins the two vertices.
The network's total length if four times the hypotenuse of a 60° right triangle whose longer leg is 50 km, plus the distance separating the two inner junctions, which is 100 km minus twice the shorter leg of the given right triangle.
That's 4*(2/sqrt(3))*50 + 100 - 2*50/sqrt(3) ~= 273.205080756888 km.
It's also 4*50/sin(60°) + 100 - 2*50/tan(60°).
As for this being the minimum, let's at least determine that it's the minimum of its kind--that is, two opposite sides of the square being indented to form two segments, where these pairs of segments are connected with a straight line--a straight line that might vanish to zero length if brought to the center, i.e., the network being the two diagonals of the square.
That latter possibility would have total length 2*100*sqrt(2) ~= 282.84271247462, which is clearly bested by what we have above.
The opposite extreme would be an H shape of total length 3*100 = 300: even worse.
Let's see if 60° is optimal for the half of the angle at the bend in the outer track on either side.
Simplified we get:
100 + 200/sin(pi/3) - 100/tan(pi/3)
We need to differentiate:
100 + 200/sin(x) - 100/tan(x)
at x = pi/3
The derivative is:
-200*cos(x)/(sin(x)^2) + 100*(sec(x)^2)/(tan(x)^2)
at pi/3 this is:
-200*(1/2)/(3/4) + 100*4/3 = -400/3 + 400/3 = 0
It's certainly a local extremum, and the endpoints mentioned above hint strongly that this extremum is a minimum rather than a maximum. Rather than differentiate again, a table should suffice to show this is a minimum:
in degrees network length
Posted by Charlie
on 2013-04-05 15:46:00