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.