connecting cities

[BMAD]

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.

[bonanova]

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.