The Travelling Santa Problem

This is a problem that briefly entertains me each year around this time, because it's mathematical and I'm me.

The question is, "How fast does Santa have to go to visit all those homes?"  We're not going to assume he has to go down chimneys or anything like that; he just has to get to all of the homes.  But assuming that Santa is real, he is still subject to the laws of physics.  No getting around those.

The Travelling Santa Problem bears a distinct resemblance to another classic problem of computation, the Travelling Salesman Problem.  A typical statement of this problem (made as non-gender-specific as I can manage) goes as follows: A sales rep must visit the capital cities of all 48 contiguous states, in whatever order desired.  What order minimizes the total travel distance?  It doesn't matter whether the sales rep drives or flies; what matters is that there is a definite and known distance between any pair of capitals.

For small numbers of capitals, this problem is trivial.  Consider three cities: Sacramento CA, Carson City NV, and Phoenix AZ.  The air distances between these cities are S-C = 160 km, C-P = 930 km, and P-S = 1016 km (I got these figures from the City Distance Calculator at http://www.geobytes.com/citydistance.htm).  The sales rep, in order to minimize the total travel distance, should avoid the long Phoenix-to-Sacramento leg, and visit the cities in the order Sacramento, Carson City, Phoenix (or the reverse).

Adding a fourth city does complicate matters somewhat.  The cost of adding one city is three new distances.  If we add, say, Boise ID, the new distances are S-B = 712 km, C-B = 580 km, and P-B = 1179 km.  And instead of only three essentially different routes, there are now twelve: B-C-P-S, B-C-S-P, B-P-C-S, B-P-S-C, B-S-C-P, B-S-P-C, C-B-P-S, C-B-S-P, C-P-B-S, C-S-B-P, P-B-C-S, and P-C-B-S.  (There are twelve other orders, for a total of 4! = 24, but the other twelve are the reverse of those already listed, and are the same for the purpose of total distance.)  By exhaustive calculation, we find that the minimal path is B-S-C-P (or P-C-S-B), with a total length of 712+160+580 = 1452 km.

One thing that becomes quickly apparent about this problem is that you can't solve it just by picking the three shortest distances, because those three distances may not connect all of the cities, or do so in a path.  Instead, in this case at least, we had to try all the different routes and pick the shortest overall route.  In fact, the Travelling Salesman Problem is a so-called NP-hard problem; this ties it with a number of other problems whose solution times are all expected to increase exponentially with the size of the problem, barring some unexpected theoretical advance.

In the case of the Travelling Santa Problem, however, we are not interested in knowing how Santa knows what order to visit the homes, or even what order he actually visits the homes.  We just need to know, to a rough order of magnitude, how far he must travel to visit every home.

Let us consider that the current population of the Earth is about seven billion.  How many homes is that (if by home we mean any single living unit)?  There are some homes with lots of people in them, living as a unit; on the other hand, there many homes with only one person in them.  We probably would not be too far off if we assume an average of two people per home.  That would mean 3.5 billion homes to visit.

Now, if these 3.5 billion homes were evenly distributed across the surface of the Earth, which has a surface area of about 510 million square kilometers, each home would have to itself an average of about 0.15 square kilometers, which means the mean home-to-home distance would be about 0.4 km, and Santa would have to travel about 3.5 billion times 0.4 km, or about 1.4 billion km.  If we assume that Santa has to travel all that way in a single day (86,400 seconds), that means he must travel about 16,000 km/s, a little over a twentieth of the speed of light.  So, very fast (about 35 million mph), but at least doable in principle.

In truth, it's a bit better than that.  In the first place, most of the Earth's surface is water; only about 30 percent of it is land.  Of that, the polar lands, especially around Antarctica, are not readily habitable in the usual way, so that perhaps only about 25 percent of the Earth's surface has any appreciable habitation.  That cuts the total distance in half to about 700 million km, and the necessary speed to 8,000 km/s.

Even better, human homes are not evenly distributed across the 25 percent of the Earth's surface they cover, but are clumped together in towns, villages, and cities large and small.  We might consider a clump to be any collection of homes that are within 100 meters of at least one other home.  This means, among other things, that a single isolated home is considered to be a clump.

It's hard to know the exact number of such clumps in the world, but perhaps we would not be too far off if we let the average clump size be 350 homes.  In that case, the total number of clumps would be 3.5 billion, divided by 350, or 10 million clumps.  The average clump-to-clump distance would then be about 7 km, and the total clump-to-clump travel distance would be 10 million times 7 km, or 70 million km.  To that would have to be added the home-to-home travel in each clump of 350 homes.  If each pair of homes is separated by 100 meters, and there are 350 homes, then each clump requires an additional 35 km, times 10 million clumps, or 350 million km, for a grand total of 420 million km.  That cuts the necessary speed to just under 5,000 km/s.

Of course, 100 meters is just the maximum cutoff distance between homes in a clump.  The average distance would be rather smaller.  In a major city like New York, for instance, the average distance is probably closer to 10 meters; in other areas, the average might be smaller than that.  In that case, the total clump internal distance for 350 homes would be more like 3 or 4 km, for a total distance of 100 million km, with a required speed of about 1,200 km/s.

Finally, statistical studies show that if N clumps are randomly distributed over an area of about A = 130 million square kilometers (as we've assumed here), the unevenness caused by that random distribution creates some clumping in the clumps, so that the total clump-to-clump travel distance is given approximately by  √(NA/2) = √(650 million million square kilometers) = 25 million km, lowering the total distance to 60 million km, and the speed to 700 km/s.

That's still about 1.6 million mph—fast enough to go around the Earth in a single minute—so perhaps Rudolph better get going.