Did Santa use Google maps?

Roberto Saracco December 27, 2017 Blog 545 Views

What is the most effective path for Santa to deliver the presents to kids in all counties in the US? It is a difficult problem to solve, actually impossible without today’s supercomputing power. Credit: Time magazine

Well, we take for granted that Santa knows the way to deliver all the presents to the million of kids around the world but we seldom stop considering the challenge he is facing.

He starts from the North Pole at midnight with his sleight pulled by the reindeers. Yes they are fast, and fly (only Santa’s reindeers do…), still he has to minimise the path connecting all the kids and finding the shortest path is a huge problem. Mathematicians call this the “salesman problem”: a salesman has to meet a certain number of clients spread in different cities and has to find out the most effective way to visit them all. Effective may mean the shortest distance, the shortest time, the cheapest roads… It doesn’t matter the criteria you apply. The problem of finding the most effective path gets more and more difficult (computational intensive) as the number of clients grow.

The problem facing Santa is mind boggling: just looking at delivering in the US and considering the most effective path among the 3108 Counties (and not going to to the 36 million + kids waiting for his presents) the possible paths are 1,568 followed by 9,500 zeros! We don’t even have a name for that number (consider that the number of atoms in the universe is estimated to be a number with 78 up to 82 zeros…. basically nothing if compared to the number of choices facing Santa just in the US).

The full path suggested by Time for Santa delivery in the US. The total travel path would have been 88,639 miles to cover the 3,108 Counties in the US. Credit: Time

Any attempt to solve this “salesman problem” is computationally intensive, i.e. it requires a lot of computation power, farther exceeding the one available to our brain and even to the most powerful supercomputers. There is no algorithm for a straightforward solution but there are a number of strategies to approximate the best possible path.

A number of mathematicians have been at work on this problem to help Santa in this year tour. Google has provided a map for what they feel may be a good path, NORAD has done the same, of course resulting with a different strategy.

Still there is no proof that any of these would be the best one. It shows that there is still a lot of unsolved problems ahead that our present technology is not able, yet, to meet.

Luckily Santa is way smarter than us and he managed to deliver, on time!