2014 AMC 12B Problem 23

2014 AMC 12B 23. The number 2017 is prime. Let S = \displaystyle\sum\limits_{k=0}^{62} \binom{2014}{k}. What is the remainder when S is divided by 2017?

(A) 32   (B) 684   (C) 1024   (D) 1576   (E) 2016

I was quite puzzled when I first saw this question. If the modulus we are working with is 2017, why is the “numerator” of the binomial coefficients 2014, and not 2017? Also, why does the summation go from 0 to 62? How is 62 related to 2014 and/or 2017? There doesn’t seem to be any link. I was also quite sure that the solution to the problem was not calculating 63 remainders by brute force and adding them.

The first line of attack we could try with this problem is to see if we can apply any established combinatorial identities. Unfortunately it doesn’t seem to be the case. Wikipedia claims that there is no closed formula for \sum\limits_{i = 0}^k \binom{n}{i}. The following 2 formulas are the most commonly used ones, could we use them?

\begin{aligned} \binom{n}{k} + \binom{n}{k+1} &= \binom{n+1}{k+1} \\  \binom{n}{n} + \binom{n+1}{n} + \dots + \binom{n+k}{n} &= \binom{n+k+1}{n+1} \end{aligned}

The second one doesn’t seem so suitable as the “numerator” of the binomials are not constant. The first has some promise, but an application of it doesn’t seem to lead anywhere:

\displaystyle\binom{2014}{0} + \binom{2014}{1} + \dots + \binom{2014}{62} = \begin{cases} \binom{2015}{1} + \binom{2015}{3} + \dots + \binom{2015}{61} + \binom{2014}{62}, \\  1 + \binom{2015}{2} + \binom{2015}{4} + \dots + \binom{2015}{62}. \end{cases}

While the second cases looks a bit cleaner with all the “numerators” being the same, there is no simple formula to add binomials whose “tops” are the same but “bottoms” differ by 2.

The next line of attack we could try is to write out the binomials fully and simplify them as much as possible. Since we are working modulo 2017, it seems like it would be better to consider numbers (such as 2014) which are closer to 2017 as negative numbers instead: e.g. 2014 \equiv -3 \mod 2017.

\binom{2014}{0} = 1 is simple enough. \binom{2014}{1} = 2014 = -3 \mod 2017 Let’s keeping going up the binomials in the sequence:

\begin{aligned} \binom{2014}{2} &= \frac{(2014)(2013)}{1 \cdot 2} \\  &\equiv \frac{(-3)(-4)}{2} &&\mod 2017 \\  &\equiv 6 &&\mod 2017. \end{aligned}

\begin{aligned} \binom{2014}{3} &= \frac{(2014)(2013)(2012)}{1 \cdot 2 \cdot 3} \\  &\equiv \frac{(-3)(-4)(-5)}{2 \cdot 3} &&\mod 2017 \\  &\equiv -10 &&\mod 2017. \end{aligned}

We are on to something! Notice how there was a cancellation in the fraction for \binom{2014}{3}? Let’s see it for \binom{2014}{4}:

\begin{aligned} \binom{2014}{4} &= \frac{(2014)(2013)(2012)(2011)}{1 \cdot 2 \cdot 3 \cdot 4} \\  &\equiv \frac{(-3)(-4)(-5)(-6)}{2 \cdot 3 \cdot 4} &&\mod 2017 \\  &\equiv (-1)^4 \frac{(5)(6)}{2} &&\mod 2017 \\  &\equiv 15 &&\mod 2017. \end{aligned}

Following this pattern, we obtain the following:

\displaystyle \binom{2014}{0} + \binom{2014}{1} + \dots + \binom{2014}{62} \equiv 1 - \frac{2 \cdot 3}{2} + \frac{3 \cdot 4}{2} - \frac{4 \cdot 5}{2} + \dots + \frac{63 \cdot 64}{2} \mod 2017.

If we can’t think of any other bright ideas, we could just add up these 63 numbers and divide by 2017, it’s certainly a lot easier than the original 63 numbers that we had to compute and add. However, noticing that \frac{n(n+1)}{2} is simply the sum 1 + 2 + \dots + n:

\begin{aligned} RHS &= +1 \\  &\hspace{1em} -1 - 2 \\  &\hspace{1em} +1 +2 +3 \\  &\hspace{3em} \vdots \\  &\hspace{1em} +1 +2 +3 \dots +63 \\  &= 1 + 3 + \dots + 63 = (32)^2 = 1024.\end{aligned}

Thus S \equiv 1024 \mod 2017, the answer is (C).

Advertisements
This entry was posted in Grade 12, USA and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s