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?


Solution
So maybe you thought this was the shortest:
If so, you would be wrong... This is not the shortest answer!

Give it a bit more thought. Find a solution shorter than 2×√2 ≈ 2.83 km.
Got it?

3 comments:

  1. But can you prove that that is the best?

    ReplyDelete
  2. What if it were in a shape of a "Z"?
    One side would be 1 unit, the bottom side would be another unit and the diagonal side would be ~1.4 units, so it's 2.4 units. That's less than both of these and connects each point in a single line, amirite?

    ReplyDelete
    Replies
    1. Sorry, you forgot to count one... 1+1+1.4 comes to 3.4! ;)

      Delete