BMAD 64 Posted September 23, 2013 Report Share Posted September 23, 2013 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. Quote Link to post Share on other sites

0 Solution bonanova 84 Posted September 23, 2013 Solution Report Share Posted September 23, 2013 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. Quote Link to post Share on other sites

## Question

## BMAD 64

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

## Join the conversation

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