Home / Blog / Did Santa use Google maps?

Did Santa use Google maps?

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!

About Roberto Saracco

Roberto Saracco fell in love with technology and its implications long time ago. His background is in math and computer science. Until April 2017 he led the EIT Digital Italian Node and then was head of the Industrial Doctoral School of EIT Digital up to September 2018. Previously, up to December 2011 he was the Director of the Telecom Italia Future Centre in Venice, looking at the interplay of technology evolution, economics and society. At the turn of the century he led a World Bank-Infodev project to stimulate entrepreneurship in Latin America. He is a senior member of IEEE where he leads the New Initiative Committee and co-chairs the Digital Reality Initiative. He is a member of the IEEE in 2050 Ad Hoc Committee. He teaches a Master course on Technology Forecasting and Market impact at the University of Trento. He has published over 100 papers in journals and magazines and 14 books.

One comment

  1. I was asked: “how do you get that number?”. Well, it is the factorial (n!) of the number of Counties Santa has to visit (3108!). To get the number you have to multiply 1*2*3*4*5*….*3108