Monday, 24 December 2012

Santa’s job is harder than you think!

Who wouldn’t want to be Santa? You work one day a year, people give you mince pies and you spend the rest of your time deciding who’s naughty and who’s nice. However, Santa’s job is more difficult than you might think and he is certainly a mathematical genius who could win $1,000,000!

Efficient packing is an Elf's forte.
Let’s focus on just two of his important tasks. Firstly, he has to pack his sleigh full of toys. Annoyingly, toys are not all the same shape so how does he efficiently pack his sleigh? Either he is excellent at Tetris, or he has managed to solve an extremely difficult maths problem known as “bin packing”. The problem is, simply stated, ‘given a fixed amount of space and packages of different sizes, is there a complete list of instructions that will allow you to make the most of the space?’

Santa's problems are bigger than his belly.
The second problem he faces is finding the quickest route around Earth that visits every house. This is known as the “travelling salesperson problem”. Is it possible to find a recipe that will always give you the fastest route?

In both cases no one knows the answer. What is worse is that we don’t even know if there is an answer! Mathematicians describe these problems as “NP” (Not Polynomial). This means that the difficulty of finding the best solution increases dramatically whenever you add another package or house.

Although these problems may be placed in fantasy, real life logistic companies face these obstacles every day and solving them would save a fortune. In fact, the solutions are so important that the Clay Mathematics Institute offers one million dollars to anyone who can either produce a method that works flawlessly, or show that one doesn’t exist.

So until Santa decides to retire and give up his secrets, that million is waiting for the right mind. Who knows? It could even be yours.

Merry Christmas from the Laughing Mathematician and see in 2013 for a new set of posts on the gömböc.
A very seasonal Turing pattern.

Although we may not able to solve the problem yet we can still take a peak at Santa's solution. The United States and Canada aerospace defence organisation, known as NORAD, take it upon themselves to track Santa every year as he travels around the globe. You can follow Santa's journey through their website,
A previous NORAD tracked route of Santa's.

An abridged version of the above post first appeared in the Oxford Mail 20/10/12.