All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Neat Network II (Posted on 2013-04-05) Difficulty: 3 of 5
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.

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution assuming there's no other topological configuration | Comment 2 of 4 |

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information