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!

Advertisements

4 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. 🙂

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: