The cabinet of Road Island was in session. The Minister of Transport was pointing to a map of the island and saying: ‘It is essential for the good of our economy that we develop a good highway system. Now the hay-producing towns A, A' need to be linked by a highway, as do the apiary towns B, B'. The seaside ports C, C' need a joining road, and there should be ease of transport between the holiday centres E, E'.’

‘It looks as though we shall need some intersections,’ said the Prime Minister.

‘That might be dangerous,’ answered the Minister of Health, ‘as both our hospital beds are occupied.’

‘Overpasses or tunnels are out too,’ said the minister of Finance. ‘No money!’

‘Well, we can’t afford an expensive consultant,’ said the Prime Minister sadly. ‘I know, let’s ask the readers!’

Hint 1

There is something slightly funny about this title.
What is it?

Hint 2

(Unhelpful hint!) There is of course always the possibility that there might not be a solution!

Solution

A solution is given in the sketch below. Although this problem is quite simple to solve, it is important to sketch the roads in the right order. For example, first linking C and C', or E and E' will cause problems with the other roads.

Extensions

This problem of non-intersecting paths brings us to the area of topology again.

1. Suppose the island has three towns which we wish to connect by non-intersecting roads in every possible way. Can you give a solution?

2. Now suppose that the island has four towns which are to be connected in every possible way. Can you solve this?

3. What if the island has five towns to be connected in every possible way?

Hint 1

Hint 2

Solution

Extensions