Why do this problem?

As well as encouraging students to work systematically, this problem introduces ideas from Decision Maths and Computer Science such as the Travelling Salesperson problem and the efficiency of algorithms.
 

Possible approach

Hand out this worksheet and encourage students to work on their own or in pairs on the first part of the problem with four cities. Bring the class together to discuss the sort of strategies they used to find a short route, and to discuss the checking that was necessary to be sure that their route was the shortest.

Once students are happy with the idea that a 'brute force' algorithm that checks every possibility is the ONLY way to be certain of finding the shortest route, set them the second challenge to find the shortest route when there are five cities.

"You need to be able to convince everyone that the route you find is the shortest. Think about how you could record your work to make sure you don't miss any possible routes."

While students are working, circulate and notice anyone who is using a particularly useful representation such as a systematic way of listing possible routes, or a tree-diagram approach. Bring the class together and invite those students to share their representations.

"Why does it take longer to check all the routes for five cities than four?"
"Is there a quick way to work out how many different possible routes there will be, for six cities?"
"How will the number of possible routes continue to grow?"

Finally, as students begin to get some appreciation of the way the number of routes grows as the number of cities increases, challenge them to work out the time taken to implement the brute force algorithm by computer.

Key questions

How can you represent the different routes in a way that makes sure you don't miss any?

If I add in an extra city, how does that affect the number of different possible routes?

Possible extension

There are rich opportunities for students to go and research topics in Decision Mathematics and Computer Science and to learn about the challenges involved in seeking solutions to problems using computers.