snapsvg

2014-12-22

Day 22 - The nth Day Of Christmas

How many presents were given, in total, on the 12th day of Christmas, by the so-called "true love"? How many for the nth day?

For each day we know that each other day was done again, so we have a shape like this:

1
12
123
1234
...

Each column is as tall as the number of rows, and the number of rows is 12.

This means the 1 column is 12 tall, the 2 column 11, and so on.

This is 12 * 1 + 11 * 2 + 10 * 3 ...

That's boring. That's not what computers or maths are for. Let's generalise.

We can see that each section of the summed sequence follows a pattern of x * y, where x + y = 13.

It is common, when analysing sequences, to forget that the order matters, and the row number can be used as a variable. If we call that variable i then each section is (13 - i) * i, and the total is the sum over 1, 12.

 12
  Σ (13 - i) * i
i=1

13 is suspiciously close to 12. What happens if we do this?

 12
  Σ (12 + 1 - i) * i
i=1

And then replace the 12 with our n to answer "What about the nth day?"

  n
  Σ (n + 1 - i) * i
i=1

Does it work? Let's Perl it up. Each value of (n + 1 - i) * i can be produced by a map over the range 1..$n, using $_ in place of i, since that's exactly what it is in this case.

sum0 map { $_ * ($n + 1 - $_) } 1 .. $n

sum0 comes from List::Util, and does a standard sum, except the list is assumed to start with zero in case the list is empty - this just avoids pesky warnings.

Try it. Using $ARGV[0] for $n we can give our n on the command line:

perl -MList::Util=sum0 -E'say sum0 map { $_ * ($ARGV[0] + 1 - $_) } 1 .. $ARGV[0]' 12

Vary the 12 to solve for different values of n.

The answer, incidentally, is 364.

No comments:

Post a Comment