Why take the Traveller Challenge?

This challenge encourages you and your family to think about the mathematical idea of optimisation. Optimisation exists in many decisions that we make.

By trying to find the shortest route someone could take on their travels you will discover the complexity involved in optimisation processes.

Watch Laura introduce the Traveller Challenge.

Download transcript in {Word} or {PDF}

Connections to real life

Optimisation exists in may decisions that we make. From planning and logistics to even drilling holes in a circuit board, the concept of optimisation can be applied. It is integral to computer science.

With self-driving cars possibly appearing on our roads in the future, computers onboard these cars will use optimisation strategies to find the most efficient travel routes to take.

1. Setting the scene

This challenge is based on ‘the travelling salesman problem’ – a mathematics and computer science problem, which asks what is the quickest route a traveling salesman might follow when he has a number of towns to visit on a given day.

Did you know that there are over 180,000 possible combinations of ways to visit 10 different cities? The formula to calculate this is: (number of cities – 1) 1/2

For ten cities that’s (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2)/2 = 181,440

To find out how many possible combinations there are for 16 places type 15!/2 into Google. Can you say that number in words?

Links to the curriculum

Measurement and Geometry, Levels 4-10

Maths words

optimisation – finding the best solution for any given situation.

approximation – finding a result that is close to the answer.

Find more maths words in the Glossary.

2. The Challenge

Find the shortest route a traveller could take.

  1. Split into teams. You may like to work by yourself or pair up with another person.
  2. Print a copy of this worksheet for each team member. If you don’t have access to a printer you can draw your own copy.
  3. Moving from point A, visit every red dot and return to Point A.
  4. Count your total travel distance. Each two dots you travel between counts as 1.
  5. Try more combinations. See if you can get your total distance as low as possible.
  6. After 10 minutes, see which team has the smallest total travel time.
  7. Discuss how you worked through the problem.

Coach Chloe’s advice

3-Coach-Chloe.fw

Hi, I’m Coach Chloe. If you are stuck, I have some questions and suggestions that might help.

There are more than 180,000 solutions to this question so you are going to need to use a method of guess and check might be useful. After you have a route you like, try making small changes to slowly improve your answer.

You could make a list each route you try like this A-K-L-N-M-H-I-G-J-E-B-D-C-F-A.

You could also make a table of the combinations you try like this:

Route Distance
A-G-E-C-B-F-D-I-H-K-L-M-N-J-A 74
A-K-L-N-M-H-I-G-J-E-B-D-C-F-A 60

3. Keep going

Find the best place to place a hardware store.

  1. Split into teams. You might like to change teams at this point.
  2. Print a copy of this sheet for each team. If you don’t have access to a printer you can draw your own copy.
  3. Decide where the best place for a hardware store might be to minimise travel distance.
  4. Count your total travel distance for a person in each location to travel one way to the hardware store. Each two dots you travel between counts as 1.
  5. Try more combinations. See if you can get your total distance as low as possible.
  6. After 10 minutes, see which team has the smallest total travel time.
  7. Discuss how you worked through the problem.