a Christmas brain teaser

When finding some math worksheets to occupy my six year old daughter on her day off of school, I discovered a Christmas brain teaser for elementary students (in pdf format):

Find a route [between twelve cities] for Santa to follow that is as short as possible. After you have found a route, compare it to others to see if they found a shorter route.

Of course, you will immediately recognize this as the TSP.  The “solution” is amusing:

Try to view this question as open-ended, or your student(s) might be working on it for days. …And if someone figures out the best answer to this question, please let me know and I’ll add it here.

Finding the optimal solution to a twelve city TSP is indeed pretty hard.  So hard, in fact, that the folks at math-drills.com couldn’t find the solution.  I have confidence that my readers can find the optimal solution in less than a day.  But please spend Christmas with your families enjoying holiday cheer.

Happy holidays!


5 responses to “a Christmas brain teaser

  • Paul Rubin

    The optimal solution goes 30,071 miles (assuming the reindeer make it into Warsaw without being distracted by any reindeer hotties as they pass near Finland).

  • Laura

    You are amazing, Paul!

  • Brent Hauble

    On my first attempt I got an answer of 26,651. I started by finding the shortest distance of London to Paris, then I would pick the shortest remaining distance and repeat. The last stop was Sydney.

    It may be possible to go even shorter by starting with the city that is most out of the way (probably Sydney) and then choosing the shortest route remaining route.

  • Paul Rubin

    Hmmm. Maybe this isn’t a TSP after all. Looking back, the instructions do not explicitly say the loop must be closed. (Brent’s solution, by the way, adds up to 37,215 if you do in fact close the circuit.) The shortest simple path appears to have length 21,694.

    Idle hands are indeed the devil’s workshop. 🙂

  • Santa Claus’ Supply Chain – young SCholars

    […] Vehicle Routing Problem: However, the main problem that Santa and his associates face is the problem of route planning. Santa has to define not only the number of trips necessary to deliver all the presents but also the optimal routes for each of these trips. Santa seems to find himself in the situation of having to solve several travel salesman problems (TSPs): “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”. If you would like to try solving one of these TSPs for Christmas with your children or friends, a few years ago Professor Laura Albert reported one of them on her blog Punk Rock Operation Research. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: