BrainDen.com - Brain Teasers
• 0

# connecting cities

## Question

There are four cities located on the vertices of a square. Your task is to design a network of roads such that (1) every city is connected with every other city, and (2) the total length of the roads is minimized. The roads can intersect each other.

## Recommended Posts

• 0

This problem has a surprising solution that becomes apparent when, because of symmetry, we note the road will likely pass through the center of the square. We slice the square through the center with an E-W cut.

Now consider only the south half of the square, and minimize the road length that connects the two lower cities with the square's center. Immediately we see that the triangle they form is suboptimal: the roads from the two lower cities should meet somewhere due south (again by symmetry) of the center, at a point determined by the angle of inclination from due east of the road from the SW city. The road thus makes an inverted Y. The angle that minimizes the overall length of the Y is easily seen to be 30 degrees, and, for a unit square, that length is 2.5/sqrt(3).

The upper half of the road is a mirror image. The minimum road length is thus 5/sqrt(3) ~ 2.887 times the side of the square, and has the shape of two Ys joined at their stems.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.