Wednesday, July 27, 2011

The Town's New Roads

A small town has four important places: a factory, school, soccer stadium and the shops. These four places are located on the corners of a square exactly 1 kilometer in size (see image on the left).
Now the municipality is planning the construction of roads in between. Each location should be directly or indirectly reachable from any other location. Extra intersections can be placed wherever. However, because of cutbacks, the designers are instructed to plan as little road as possible.

Here are some attempts to do that.
  1. The first image connects all places directly to every other place. While this makes for fast travelling, it doesn't quite result in a small amount of road. The total length here is 4×1 + 2×√2 ≈ 6.83 km.
  2. Since indirect connections were fine, the second image does away with the diagonals giving it a total road length of 4 kilometers.
  3. Looking for even shorter solutions, what happens if the road is built in the shape of a circle, touching every location? With π×√2 ≈ 4.44 km, that third image is worse.
  4. So in the last image, one of the roads is removed from the square, making a total of 3 km. While moving from the factory to the shops will be a pain, it is the shortest solution so far. Although an H-shape would be more practical, this is not relevant to the problem (that's still 3 km).
But 3 kilometers is not the shortest solution. What is?