AMC 10 · 2014 · #23
Grade 11 number-theoryPick an answer.
C(2014, 62) has more than a hundred digits, so nothing can be computed head-on. The one exploitable fact is that 2014≡ -3 (mod 2017): the top of the binomial is a tiny negative number. Writing C(2014, k) as a product of k descending factors over k! (Tool #15) and replacing each factor by its residue turns every giant term into the tiny triangular number C(k+2, 2) with an alternating sign — a genuinely easier related problem (Tool #9). What is left is a 63-term alternating sum of triangular numbers, which splits into a lone first term plus 31 neighbouring pairs (Tool #7, Tool #16); each pair collapses to a single odd number by an exact algebraic identity, not by reading a pattern off a short list. Summing the resulting odd numbers (Tool #5) gives a number that must finally be checked to lie below 2017 before it can be called the remainder (Tool #3).
Shrink the top index modulo 2017
The top index shrinks to something small.
A prime modulus lets you cancel any factor smaller than it, so small factorials behave like ordinary divisors.
4.OA.B.4Solve An Easier Related ProblemWrite the binomial as a descending product
The coefficient is a descending product.
Choosing k things in order and then dividing out the k! orderings keeps only k factors in sight.
11.S-CP.B.9Organize Information In More WaysCollapse each term to a triangular number
Each term collapses to a triangular number.
A hundred-digit binomial and a two-digit triangular number can be the same thing mod 2017, because only the residues of the factors survive.
9.A-SSE.A.2Solve An Easier Related ProblemRewrite the whole sum
The whole sum rewrites with alternating signs.
Once every term is rewritten, the modulus can be set aside and an ordinary integer sum finished exactly.
7.EE.A.2Identify SubproblemsPair neighbours using an exact identity
Pairing neighbours leaves the odd numbers.
Consecutive triangular numbers differ by exactly the counting number between them, so every pair collapses to one odd number.
Consecutive triangular numbers differ by exactly the counting number between them, so every pair collapses to one odd number.
▸ Why?
Each triangular number is the one before it plus the next counting number, so the difference is that number.
▸ Why?
Adding two consecutive triangular numbers instead gives a square, so the pairs total in a fixed pattern.
Add the odd numbers
They add to a perfect square, 1024.
Odd numbers taken from both ends of the list always pair to the same total, so the sum is just that total times the number of pairs.
6.EE.A.3Look For A PatternConfirm this is the remainder
It is already in range, choice (C).
A remainder is the one representative of the congruence class that fits between 0 and the divisor.
4.NBT.B.6Eliminate PossibilitiesBecause 2014 is only 3 below the prime 2017, every huge binomial shrinks to a small triangular number with an alternating sign, and pairing neighbours turns the whole sum into 1+3+5+…+63=32².
- Shrink the top index modulo 2017
- Write the binomial as a descending product
- Collapse each term to a triangular number
- Rewrite the whole sum
- Pair neighbours using an exact identity
- Add the odd numbers
- Confirm this is the remainder