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.

- 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.
- Since indirect connections were fine, the second image does away with the diagonals giving it a total road length of 4 kilometers.
- 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.
- 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).

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?

But can you prove that that is the best?

ReplyDeleteWhat if it were in a shape of a "Z"?

ReplyDeleteOne 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?

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

Delete