Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 10"
(→Solution 2) |
|||
Line 26: | Line 26: | ||
==Solution 2 == | ==Solution 2 == | ||
− | <math>\sum_{k=0}^{n} {n | + | <math>\sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} =2^n</math>, and <math>\sum_{k=0}^{3n} \begin{pmatrix} 3n \ 3k \end{pmatrix} =2^{3n}</math> |
<math>\sum_{k=0}^{3n} | <math>\sum_{k=0}^{3n} | ||
Line 41: | Line 41: | ||
<math>{2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}=\sum_{k=0}^{3\times 669} | <math>{2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}=\sum_{k=0}^{3\times 669} | ||
− | |||
== See also == | == See also == |
Revision as of 11:00, 25 November 2023
Contents
[hide]Problem
Compute the remainder when
is divided by 1000.
Solution
Let and
be the two complex third-roots of 1. Then let
.
Now, if is a multiple of 3,
. If
is one more than a multiple of 3,
. If
is two more than a multiple of 3,
. Thus
, which is exactly three times our desired expression.
We also have an alternative method for calculating : we know that
, so
. Note that these two numbers are both cube roots of -1, so
.
Thus, the problem is reduced to calculating .
, so we need to find
and then use the Chinese Remainder Theorem. Since
, by Euler's Totient Theorem
. Combining, we have
, and so
.
Solution 2
, and
where
is an integer
that depends on the value of
and will make the sum an integer.
When is odd,
is odd,
, Therefore
When is even,
is even,
, Therefore
So the equation becomes:
See also
Mock AIME 4 2006-2007 (Problems, Source) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 |