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)

in radians.

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:

half-angle          total
in degrees      network length
    50            277.1714947
    51            276.3735099     
    52            275.6750804     
    53            275.0717266     
    54            274.5593427     
    55            274.1341639     
    56            273.7927380
    57            273.5318992
    58            273.3487455
    59            273.2406175     
    60            273.2050808
    61            273.2399084
    62            273.3430670
    63            273.5127026
    64            273.7471292
    65            274.0448180
    66            274.4043872
    67            274.8245939
    68            275.3043260
    69            275.8425952
    70            276.4385311

 

Posted by Charlie on 2013-04-05 15:46:00