Can you find the best route for the Olympic Torch relay to take? This more challenging activity is designed to be accessible to GCSE maths students (Key Stage 4).

Detailed teachers' notes for this activity, including worksheets, are available on our NRICH website.


The Olympic Torch Tour

In May 2012, the Olympic torch arrived at Lands End for a 70 day tour of the UK, ending in London. The plan was to cover towns and villages so that 95% of Britons would 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.


 

Further reading

You can find out more about the Olympic Torch Relay route, including maps and the ability to search by postcode for the nearest point on its route to your location, on the London 2012 website and BBC website. Sport at School have also developed an interactive Getting to the Point tool to help schools collect and share data on distances to the Olympic Torch Relay route.

The organisers of the Olympic Torch Relay have planned the route to come within 10 miles of 95% of the population - have they succeeded? Find out how close it will come to where you live and then take part in our poll. What factors might affect the reliability of our survey data? This data handling activity can be approached at a wide range of levels appropriate for students from Key Stages 2 to 4.

Detailed teachers' notes for this activity, including worksheets, together with a featured solution, are available on our NRICH website, where you can find thousands more mathematical resources including problems, investigations and games for all ages from 5 to 19.