Every year on Christmas Eve, Santa travels the globe delivering presents to children everywhere.

Santa is our culture’s only mythic figure truly believed in by a large percentage of the population. It’s a fact that most of the true believers are under eight years old, and that’s a pity.
~ Chris Van Allsburg

As we grow older and the ringing of the silver sleigh bells grow dim in our ears, we’re given to question whether or not Santa exists. Eventually, we come to the conclusion he can’t exist because his task is impossible, regardless of the attempted explanations. Or, is it?

Let’s look at some actual numbers.

The Traveling Santa Problem

 

To begin with, there are a lot of people on the planet—roughly 7.3 billion to be not so exact.

That translates to lots of houses for Santa to visit. Now, before we go on much farther, I’d like to point out that again, the mathematics, assumptions, etc., used herein are suspect. Really, I’m mostly making educated guessed (i.e., making them up as I go along), though I’ll provide links to those interested in attempting to verify my conclusions (not that I’d spend time doing that, if I were you).

“So, just how many houses?” you may ask.

Ummm… let’s go with 1,333,316,210.

That number comes off of making some really poor assumptions about household data from different countries taken over more than a decade, which is not independently verifiable (See, I said it was suspect). Throwing these semi-related numbers into a spreadsheet, doing some calculations, and we get our magic number:

Now, all we have to do to work out Santa’s route is solve the age-old Traveling Salesman Problem. How hard can that really be? We’re HPC experts, and this is the type of problem we give undergraduates to give them heartburn.

Turns out… it’s hard.

If we were to check every possible path that Santa might take, we end up with 1,333,316,210! possible routes. And, yes, that is 1.3 billion factorial. If you’re not recalling factorial off the top of your head, it’s basically:

That’s a big number.

I tried to get my computer to tell me what this number is. As you can guess, that didn’t go so well. It worked on the problem for a while, and then stopped. And, when I say it stopped, what I really meant was it crashed.

Luckily, it’s actually not necessary to get this number. The Held-Karp algorithm is capable of reducing that crazy, massive O() estimate to simply be:

That should be easier to calculate, right? (Easier only counts in cases where it’s possible).

1,333,316,210² is pretty straightforward.

However, as it turns out, 2^{1,333,316,210} is a rather large number (not that 1.7 quadrillion is anything to sneeze at).

Unable to find a page conveniently listing the powers of two beyond 2²²², I had to try other means. An online exponents calculator quickly, confidently and incorrectly informed me the answer was Infinity. While I give props to the coders for not having their application simply fall over crying, it wasn’t so helpful in my case.

So, I wrote up a couple of test scripts, and then set a computer on the task of getting as far into the problem as possible over Thanksgiving week. Here’s as far as I got:

If you’re really interested, you can download the file containing the entire number.

Now, you may point out this result seems to have taken a long time to come up with an incorrect answer. Fair enough. My defense is:

1. I have a slow workstation.
2. I did a brute-force calculation because:
   • Laziness is one of the Three Great Virtues of a Programmer.
   • My workstation didn’t have anything to do over the holiday, and I didn’t want it to feel lonely.
   • The following chart doesn’t have a column for “Once in a Lifetime.”

xkcd: Is It Worth the Time (#1205)

So, as I’m sure you all expected, we’re at another impasse. Clearly, if Santa is using a supercomputer to calculate his course, it’s well beyond our current capacity. I also strongly suspect if he were using the same technology as us, our satellites would notice the oasis at the North Pole caused by the heat dissipation.

Now, it is possible that instead of traditional HPC gear, Santa is sporting a super-advanced quantum computer to provide his route. As it happens, the Traveling Salesman problem maps well to quantum computing. In 2013, one of D-Wave‘s quantum computers performed on par with the IBM/DARPS Trial Subset, a 1.5 petaFlop system with 63,360 64-bit cores on this type of problem. Now, we’re still not in the range of being able to calculate the answer to Santa’s problem, but perhaps he has a quantum computer supporting several orders of magnitude more qubits than our current systems.

Taking everything into account, I’m going with “Santa has an advanced quantum computer” as my answer here.

But Still…

There’s still the problem of the travel. How can he possibly cover all of that distance? What about the time needed to place the presents?

Let’s look at those in turn.

The first thing to consider is how close households are to each other. Now, we could assume the Earth had all of the households evenly distributed on it. Of the Earth’s roughly 510.1 million km², approximately 149 million km² are land. Thus, we get:

Interesting. In yet another unscientific step, let’s go ahead with this assumption. Granted, we are ignoring the ocean travel, but at this point there are so many bad assumptions it doesn’t really matter. Plus, because Santa will need to spiral down from the North Pole to the South Pole and then back up due to the differences in day lengths in the two hemispheres, he can minimize ocean travel by crossing between major continental groups at the South Pole.

That aside, let’s look at what the distance between households would then be. Home sizes vary around the world. In the developed world, average home sizes vary between 76–206 m². In the rest of the world, the average size is even smaller.

Arbitrarily, we’ll choose 100 m², which is a gross over-estimate that makes the math easier. Assuming the area per household and house footprint are both perfectly square, we get the followings:

So, on average, the households are 324.3 meters apart. So, now we can get total travel distance. We’ll assume he needs to get from and to his workshop, to which we’ll apply the same distance “rules” as above.

That’s nearly three times the distance between the Earth and the sun (roughly 2.89 times to be exact). We have our distance.

To calculate minimum speed, let’s temporarily assume Santa doesn’t spend any time at any of the domiciles, which is clearly bunk. At any given point in the year, the average length of the night taken over the entire globe is 12 hours.

That’s approximately 1/30th the speed of light for an absolute minimum speed. Clearly, it’s going to be faster than that, and I’d guess with stopover time, which we’ll calculate here in a minute, it’s likely to approach or exceed the speed of light, which is going to start causing all sorts of interesting relativity effects to start to come into play.

There’s another problem with this. This speed is going to have to be maintained through an atmosphere. We all love wishing on shooting stars, which are really only masses of space debris burning up as they crash through the atmosphere at frightening, yet comparably slow speeds to what we are discussing. Actually, they might as well be standing still compared to these speeds.

Now, one might think the problem is Santa and his sleigh are simply going to burn up, which they would at those speeds. But the real problem is far more dreadful. As the reindeer and sleigh started approaching those speeds the atmospheric atoms would no longer be able to get out of the way fast enough. The result would be the compression of the atoms to a point where fusion would start to occur releasing gamma radiation. In short, even if the sleigh could withstand this, Santa’s path would be a stream of thermonuclear explosions vaporizing everything he passed and effectively destroying the Earth.

xkcd: Los Alamos (#809)

As this doesn’t happen each Christmas Eve, Santa must have a different approach. Luckily, there is one, which we’ll discuss after we get a few more facts in hand.

Before we get there, we need to also know how much time Santa spends at each household. My best source on this question is the poem “A Visit from St. Nicholas” (or as it’s better known, “‘Twas the Night Before Christmas”) by Clement Clark Moore. Unfortunately, Clement did not use very scientific measures of time when describing the events he experienced. Instead he used the following, to which I’ve attached some reasonable approximations:

 
This would suggest the entire encounter took a relatively short period of time.

Assuming Clement recorded an average stop, we can calculate the entire time spent.

Hmmm… it appears we have another problem.

Yeah… and that’s without the travel time… this appears to be pushing us into the realms of magic despite everything I’m trying.

Any sufficiently advanced technology is indistinguishable from magic.
~ Clarke’s Third Law

So, let’s see what we can do here. We know Santa not only can travel at approaching-light speeds in-atmosphere without destroying all life and civilization, but also apparently has the ability to manipulate space-time.

My guess is his sleigh must be equipped with an Alcubierre drive.

For those unfamiliar, an Alcubierre drive provides the ability for faster-than-light travel in a rather interesting manner. It effectively forms a space-time fabric bubble, affectionately known as a warp bubble, around the ship (or sleigh, in our case). By contracting the space-time fabric in front of the bubble and contracting it behind, it causes the space-time fabric to effectively flow around the bubble at any desired speed, even faster-than-light. Technically, the bubble itself doesn’t ever move, so it doesn’t violate any of Einstein’s theories. In fact, it is consistent with his field equations. In other words, if one had the negative-energy and/or negative-matter required, such a drive is possible.

Additionally, the sleigh must be equipped with a device capable of localized temporal dilation would be required to deal with the “340 years in one night” paradox noted above. Otherwise, there’s no way for Santa to spend any time in any of the households. That means the sleigh is also capable of producing temporal instability in the space-time fabric, requiring power on the order of the Planck energy or roughly 10²⁸ electron volts.

That’s some engine under the hood.

It also requires a Type III civilization.

But that means…

Apparently, Santa is an alien… a visitor from another realm…

Go figure… that explains so much.

MERRY CHRISTMAS!

HAPPY HOLIDAYS!

Sources for people who really do want to attempt verification:

• Current World Population: http://www.worldometers.info/world-population/
• Number of Households per Country: http://en.wikipedia.org/wiki/List_of_countries_by_number_of_households
• Surface Area of the Earth: https://www.google.com/webhp?q=surface%20area%20of%20the%20earth#q=surface+area+of+the+earth
• Surface Area of the Earth: http://www.universetoday.com/25756/surface-area-of-the-earth/
• International House Sizes: http://www.demographia.com/db-intlhouse.htm
• Distance Between Earth and Sun: https://www.google.com/webhp?q=distance%20earth%20to%20sun#q=distance+earth+to+sun

Images courtesy of:

• Russian Space Santa – Steve Jurvetson – CC-BY-2.0
• Los Alamos – xkcd – License
• Is It Worth the Time? – xkcd – License
• Warp Drive Diagram – BigRip Wiki – CC-BY-2.0