The Olympic Torch Tour

Niharika was the only one to send us a solution this time round:

The possible routes are:

1. London-Cambridge-Bath-Coventry-London

2. London-Cambridge-Coventry-Bath-London

3. London-Bath-Cambridge-Coventry-London

4. London-Bath-Coventry-Cambridge-London

5. London-Coventry-Bath-Cambridge-London

6. London-Coventry-Cambridge-Bath-London.

I worked out the distances for each route, and they came to:

1. 336 miles

2. 296 miles

3. 372 miles

4. 296 miles

5. 336 miles

6. 372 miles

The shortest routes are routes 2 and 4.

Now imagine that each city along our route is a box. We have five boxes to line up. The first and last box must be 'London', so there is only 1 way to fill those boxes. The second box can be filled in one of 3 ways. Once we've used that city up, the third box can be filled in 2 ways. Finally when we come to the fourth box there is only 1 way to fill it in. So there are 1*3*2*1*1 = 6 routes.

I guessed that, when extending to 5 cities, we should probably start with the shortest route for 4 cities and then add the extra city in. In this case, we should start with routes 2 and 4, and add Oxford in in all the different places, and see which distance is smallest. In each case, least distance is covered if we add in Oxford between Coventry and Bath. In this case there are 6 boxes and 1*4*3*2*1*1 = 24 routes.

When there are n cities, there are n+1 boxes, and so there are $1\times (n-1)\times (n-2)\times \dots \times 2 \times 1\times 1$ routes - just think of how many ways there are to fill in each box. But if you know the shortest routes for the case of n-1 cities, my guess is that you should be able to add the n-th city to those.

Great - thanks, Niharika!