The Twelve Days of Christmas Here's a familiar Christmas song: ```On the first day of Christmas, my true love sent to me A partridge in a pear tree``` ```On the second day of Christmas, my true love sent to me Two turtle doves, And a partridge in a pear tree ``` ...and so forth, until the last verse: ```On the twelfth day of Christmas, my true love sent 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 gold rings Four calling birds Three French hens Two turtle doves And a partridge in a pear tree ``` The Puzzle: How many gifts did my true love send me? To be clear, we'll interpret the song as stating that I received one gift (the partridge in a pear tree) on the first day, and three gifts on the second day (a partridge, and two turtle doves), and so on. If you are of a mathematical bent, figure out how many gifts I would receive on the Nth day, assuming the song could continue indefinitely. Stumble It! Hints and solutions below: Hints will appear here! Try writing out the sum in rows and columns, where each row shows the number of gifts given on a particular day and each column represents a particular type of gift. For the general solution, you'll need to know the formula for the sum of the first N squares, or a little solid geometry. Here's the solution for the twelve days problem: ```1 1 + 2 1 + 2 + 3 . . . 1 + 2 + 3 + ... + 12 ------------------------------------- 12x1 + 11x2 + 10x3 + ... + 1x12 = 364 ``` From the diagram above, you can see that we get 12 partridges, 11x2 turtle doves, 10x3 french hens, and so on. Adding these up, we get 364 presents in total. One for each day of the year (except Christmas!) That's a neat solution and it requires only 12 computations, but what if our true love was exceedingly generous and continued giving gifts. Let's say she keeps it up for 1000 days. Then how many gifts would we receive? Obviously, the above technique would be too laborious, so we need to find a better solution. I'll show you one algebraic and one geometric solution. The algebraic solution is much quicker, but requires the use of a formula that may not be known to all readers. Let's start with the geometric solution. A Geometric Approach to the Solution Let's write d(k) for the number of presents we receive on day k, so that d(k)=1+2+3+...+k. We'll also we'll write S(n) for the total number of presents received from day 1 up to day n. So S(n)=d(1)+d(2)+ ... + d(n). We can represent S(12) diagrammatically as follows: The kth layer of the "tree" has d(k) points. Essentially, we've created a triangular pyramid of presents. If you know some solid geometry, you'll have come across the formula for the volume of a pyramid: V= A h / 3, where A is the area of the base and h is the height. Though we're only counting grid points on the pyramid, it's reasonable to expect that we can approximate the number of presents by the volume of the corresponding pyramid. Let's do the problem in full generality and try to compute S(n). Now the height, h, is the number of days, n. The area of the base is n*n/2. So the volume of the pyramid is V(n) = n3/6. Unfortunately V(n) doesn't ever exactly equal S(n) (indeed, often V(n) isn't even a whole number!), so let's write S(n)=V(n)+E(n), where E(n) is an error term whose value we'd like to find. It's again reasonable to guess that E(n) is a polynomial, of degree smaller than V(n). So let's write: S(n)= n3/6 + a n2+ b n + c, for some constants a, b, and c. Plugging in the values of S(0), S(1), and S(2), we arrive at: 0 = S(0) = c 1 = S(1) = 1/6 + a + b + c 4 = S(2) = 4/3 + 4a + 2b + c . from which we deduce a = 1/2, b= 1/3, and c=0. So assuming that E is indeed a quadratic polynomial, we deduce: S(n)=n3/6 + n2/2 + n/3. In particular, S(12)=123/6+122/2+12/3=364, and S(1000)=167,167,000. Note we haven't actually proved that this is the formula for S(n). Rather we've given plausible reasons for why this might be the formula. However, given our guess, one could use mathematical induction to prove the guess. I might go into this another day, but for the moment, we can contend ourselves with: An Algebraic Approach to the Solution On day k, we have d(k) = 1 + 2 + 3 + ... + k = k(k+1)/2 presents, by the formula for the sum of the first k natural numbers. By the nth day, we'll have S(n) = d(1)+d(2)+...+d(k) = 1(1+1)/2 + 2(2+1)/2 + ... + n(n+1)/2 presents. Expanding this out, we have: S(n) = (12 + 22 + ... + n2) /2 + (1 + 2 + 3 + ... + n)/2. Using the formula for the sum of the first n squares and the first n numbers, we have: S(n) = n(n+1)(2n+1)/12 + n(n+1)/4 = n3/6 + n2/2 + n/3, just as for the geometric solution. Logic Puzzles: The Twelve days of Christmas (*/**) 1 Dec 07 How many gifts did my true love send me? The squashed bee (**) 15 Oct 07 How far does the bee travel before it's squashed? 12 coins (****) 14 Oct 07 Find the counterfeit coin in 3 moves Black and blue socks (*) 28th Aug 07 Choose a matching pair of socks in the dark 100 monks (**) 18th Aug 07 How do you communicate simply by not dying? Coins on a table (***) 15 Aug 07 The last person to place a coin wins 10 Barons (***) 15 Aug 07 Help me catch a cheating Baron by weighing gold bars Fox, chicken, grain (*) 14 Aug 07 Cross a river taking only one at a time 5 pirates (****) 14 Aug 07 A tricky problem in booty allocation Try our other Puzzles: 50 states Our popular 50 states name game. England counties Name the 48 ceremonial counties of England. Asia 53 countries and territories of Asia.