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:
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?