Copyright © University of Cambridge. All rights reserved.
'The Olympic Torch Tour' printed from https://nrich.maths.org/
If you are a teacher, click here for a version of the problem suitable for classroom use, together with supporting materials. Otherwise, read on...
In May 2012, the Olympic torch will arrive at Lands End for a 70 day tour of the UK, ending in London. The plan is to cover towns and villages so that 95% of Britons will be within 10 miles of the torch relay.
Imagine a mini-Olympic torch tour running between 4 cities in the UK, with the following constraints:
- The torch starts and finishes in London
- The torch should pass each city once and only once
- The following table lists the distance between each city
(in miles as measured by Google Maps)
| |
London |
Cambridge |
Bath |
Coventry |
| London |
0 |
50 |
96 |
86 |
| Cambridge |
50 |
0 |
120 |
70 |
| Bath |
96 |
120 |
0 |
80 |
| Coventry |
86 |
70 |
80 |
0 |
- What is the shortest route?
- How can you be sure it is the shortest?
- How many different routes are there?
Let's now try a slightly longer tour of 5 cities. We'll add Oxford to the list:
| |
London |
Cambridge |
Bath |
Coventry |
Oxford |
| London |
0 |
50 |
96 |
86 |
60 |
| Cambridge |
50 |
0 |
120 |
70 |
65 |
| Bath |
96 |
120 |
0 |
80 |
54 |
| Coventry |
86 |
70 |
80 |
0 |
46 |
| Oxford |
60 |
65 |
54 |
46 |
0 |
- What is the shortest route now?
- How many different possible routes did you need to consider?
Is there an efficient way to work out the number of different possible routes when there are 10 cities? 15 cities?...
Suppose a computer could calculate one million routes per second. How long would it take to find the optimal route for 10 cities? 15 cities? 20 cities?
NOTES AND BACKGROUND
The type of question we have explored above is a famous problem in computation complexity theory known as the
Travelling Salesman Problem. Perhaps a better question for the torch tour is not to find the shortest or longest route, but to find the maximum number of cities the torch can visit whose route length is at most, say
2000 miles, or visit as many populated towns as possible. These are variants of the original problem known as the 'Orienteering Problem' and the 'Prize Collecting Travelling Salesman Problem'. It is an active area of research among mathematicians and has a wide range of applications.