Five towns

A puzzle similar to the Houses and utilities puzzle.

Puzzle

Back in the days of yore, five small towns decided they wanted to build roads connecting each pair of towns. While the towns had plenty of money to build roads as long as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed. Is it possible for each of these town to build a road to each of the four other towns without creating any intersections?

Expand

Solution

Here's one way to prove that it's not possible.

Label the towns 1 to 5. If there's a solution, then for every possible ordering of the five towns, there is a circuit route that visits all five of them in that order and returns to the first, with no backtracking.

In particular, there must be a circuit route that visits the towns in the order 1, 2, 3, 4, 5, 1 (call this Circuit A) and a circuit route that visits the towns in the order 1, 3, 5, 2, 4, 1 (call this Circuit B).

You can quickly show that Circuit B cannot be entirely inside Circuit A, nor can it be entirely outside Circuit A. Therefore, there must be at least one town (call it N) where Circuit B crosses from being outside Circuit A to being inside Circuit A.

But, as can be seen by sketching a diagram, this necessarily seperates town N-1 from town N+1 so that no road is possible between the two.

Mathematics

Coming soon!