 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Neat Network II (Posted on 2013-04-05) 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.) 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          totalin 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 - 2021 by Animus Pactum Consulting. All rights reserved. Privacy Information