The Olympic Torch Tour

Stage: 4 Challenge Level: Challenge Level:2 Challenge Level:2

 

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.


 

The NRICH Project aims to enrich the mathematical experiences of all learners. To support this aim, members of the NRICH team work in a wide range of capacities, including providing professional development for teachers wishing to embed rich mathematical tasks into everyday classroom practice. More information on many of our other activities can be found here.
Copyright © 1997 - 2012. University of Cambridge. All rights reserved.
NRICH is part of the family of activities in the Millennium Mathematics Project.