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.

n0123456...
p(n)0136101521...
P(n)01410203546...
δ1136101521...
δ223456...
δ31111...

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

[1]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:

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

We can eliminate c, first from [2] and [3] and then from [2] and [4] to produce:

[5]6a + 2b = 2
[6]24a + 6b = 7

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

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

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

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

P(n)= 16n3 + 12n2 + 13n
= 16n(n2 + 3n + 2)
= 16n(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.

0 comments: