## Saturday, 22 December 2012

### How Many Presents from my True Love?

On the first day of Christmas my true love gave to me a partridge in a pear tree.
On the second day of Christmas my true love gave to me two turtle doves and a partridge in a pear tree.
...
On the twelfth day of Christmas my true love gave to me twelve drummers drumming, eleven pipers piping, ten lords-a-leaping, nine ladies dancing, eight maids-a-milking, seven swans-a-swimming, six geese-a-laying, five golden rings, four calling birds, three french hens, two turtle doves and a partridge in a pear tree.
So how many presents did I receive all together?

This can be solved using the differences method, which is nicely explained by Ken Ward.

In the table below, n represents the day of Christmas (starting from 0, the day before I start receiving presents), p(n) represents the number of presents I receive on that day, P(n) represents the total number of presents received so far, δ1 is the first difference (the difference between successive terms of P(n) — which is p(n) of course), δ2 is the second difference (that between successive terms of δ1) and δ3 is the third difference.

 n 0 1 2 3 4 5 6 ... p(n) 0 1 3 6 10 15 21 ... P(n) 0 1 4 10 20 35 46 ... δ1 1 3 6 10 15 21 ... δ2 2 3 4 5 6 ... δ3 1 1 1 1 ...

As the δ3 values are all the same, the equation we're after is a cubic polynomial.  That is, it's of the form:

P(n) = an3 + bn2 + cn + d

Now we can do some substitution.  We can see immediately that

P(0) = 0a + 0b + 0c + d = 0 ⇒ d = 0

And now, from the next three terms, we can create 3 simultaneous equations:

P(1) = a + b + c = 1
P(2) = 8a + 4b + 2c = 4
P(3) = 27a + 9b + 3c = 10

We can eliminate c, first from  and  and then from  and  to produce:

6a + 2b = 2
24a + 6b = 7

From which we can deduce that (24 – 18a) = 1 ⇒ 6a = 1, or a = 16.

Substituting that back in , we find that 1 + 2b = 2 ⇒ 2b = 1, or b = 12.

Finally we can use  to determine that 16 + 12 + c = 1, or that c = 13.

Now we can substitute these values back in  and tidy up a bit:

 P(n) = 1⁄6n3 + 1⁄2n2 + 1⁄3n = 1⁄6n(n2 + 3n + 2) = 1⁄6n(n + 1)(n + 2)

So, by the 12th day of Christmas I will have received 16.12(12 + 1)(12 + 2) or 2.13.14 = 364 presents. Not bad going.