Jump to content
BrainDen.com - Brain Teasers
  • 0

connecting cities


BMAD
Go to solution Solved by bonanova,

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.

Link to post
Share on other sites

1 answer to this question

Recommended Posts

  • 0
  • Solution

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.
Link to post
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...