My dad and I were bored at a Christmas concert lately, so we started
talking about how many items you receive in the 12 days of Christmas.
You get 1 item on day 1, 3 items on day 2, 6 on day 3, etc. We
figured that out pretty easily, but then we were trying to come up
with a closed form solution for any number of days.
When I got home and had some paper to work with I managed to do it,
but I felt like my approach wasn't very nice.
So, can you find a solution, and more importantly do you know an
elegant way to do it?
If you're not familiar with the song, you can find the basic structure of the lyrics on Wikipedia, or just Google "the 12 days of Christmas" and you'll find it.
Just to be clear, it is a cumulative song, so you receive one partridge in a pear tree on the first day, then on the second day you receive two turtle doves and another partridge in a pear tree, for a total of four items on the first two days, and so on for twelve days. The puzzle is to find out how many gifts you receive in total for all twelve days (not just on the twelfth day), and to find an elegant way to calculate the number of gifts you'd receive if the number of days is extended beyond twelve.
You can see the solution here.
9 comments:
Dammit, you stole my Christmas exercise for this year; now I have to find something else. The number of gifts given in n days is the nth tetrahedral number n(n+1)(n+2)/6.
[(1+n)n]/2
Legend says some famous mathematician (Euler?) figured this at a young age when asked on the first day of class to add all numbers up to 100 just to keep the kids busy.
programmingpraxis,
My solution will be more about how to derive the formula than about coding a solution, so you could probably still use it.
anonymous,
That's part of the answer. That formula gives you the number of gifts on a single day.
Jaime,
Yes, that's one of my favorite stories about Euler! :)
Bill the Lizard,
When I read your puzzle the Euler story just came to my mind. Then anonymous said (n+1)n/2 which sounded totally right to me.
But it seems like I might misunderstand the puzzle since you said that the formula only give the numbers of gifts on a single day.
This was my thinking. When the song said for instance that we would be receiving 3 items on the second day they implied that was 1 item for the first day and 2 items for the second. In which case anonymous answer is totally correct.
Since it seems not to be correct, then the only other interpretation that comes to my mind is that we receive as many items each day and you still receive the items of past days. In the example before then it would be 1 for the first day and 3 for the second so 4 items in total. Is that right? can you clarify this a little bit?
Thanks!,
Pedro Melendez,
Yes, your second interpretation is correct. You receive one partridge in a pear tree on the first day, then on the second day you receive two turtle doves and another partridge in a pear tree, for a total of four items on the first two days.
I'll edit the post to clarify that point this evening, then I'll post the full solution later this week. Thanks for reading!
The story about adding the numbers from 1 to 100 is about Gauss, not Euler. It also may not be true. See Mythology here: http://en.wikipedia.org/wiki/Carl_Friedrich_Gauss
@Tim Kington
Thanks for the link... I have heard that story so many times with different actors (Euler, Pascal, Newton and now Gauss) that I would say probably was none of them. Anyway it is a very cool mnemonics to remember how to sum elements in a natural numbers sequence :)
Tim,
Whoops! You're right, that story is most commonly attributed to Gauss, not Euler. I even repeated it here a few years ago and I still conflated the two.
Post a Comment