Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 10"
(→Solution) |
(→Solution 2) |
||
(27 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
Compute the [[remainder]] when <center><p><math>{2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}</math></p></center> is divided by 1000. | Compute the [[remainder]] when <center><p><math>{2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}</math></p></center> is divided by 1000. | ||
+ | |||
==Solution== | ==Solution== | ||
− | Since | + | <!--By the [[binomial theorem]], note that |
+ | |||
+ | <cmath>\begin{eqnarray*} (1 + 1)^{2007} &=& {2007 \choose 0} + {2007 \choose 1} + \ldots + {2007 \choose 2007} = 2^{2007}\\ | ||
+ | (1 + \mathrm{cis} 120)^{2007} &=& {2007 \choose 0} + {2007 \choose 1} \mathrm{cis} 120 + \ldots + = -1 \\ | ||
+ | (1 + \mathrm{cis} 240)^{2007} &=& {2007 \choose 0} + {2007 \choose 1} \mathrm{cis} 240 + \ldots + = -1 \\ | ||
+ | \end{eqnarray*}</cmath> | ||
+ | |||
+ | If we add all three of these up, we get (since <math>\mathrm{cis} 120 + \mathrm{cis} 240 = -1</math>) the desired expression above. Hence we want | ||
+ | --> | ||
+ | Let <math>\omega</math> and <math>\zeta</math> be the two [[complex]] third-roots of 1. Then let | ||
+ | |||
+ | <math>S = (1 + \omega)^{2007} + (1 + \zeta)^{2007} + (1 + 1)^{2007} = \sum_{i = 0}^{2007} {2007 \choose i}(\omega^i + \zeta^i + 1)</math>. | ||
+ | |||
+ | Now, if <math>i</math> is a [[multiple]] of 3, <math>\omega^i + \zeta^i + 1 = 1 + 1 + 1 = 3</math>. If <math>i</math> is one more than a multiple of 3, <math>\omega^i + \zeta^i + 1 = \omega + \zeta + 1 = 0</math>. If <math>i</math> is two more than a multiple of 3, <math>\omega^i + \zeta^i + 1 = \omega^2 + \zeta^2 + 1= \zeta + \omega + 1 = 0</math>. Thus | ||
+ | |||
+ | <math>S = \sum_{i = 0}^{669} 3 {2007 \choose 3i}</math>, which is exactly three times our desired expression. | ||
+ | |||
+ | We also have an alternative method for calculating <math>S</math>: we know that <math>\{\omega, \zeta\} = \{-\frac{1}{2} + \frac{\sqrt 3}{2}i, -\frac{1}{2} - \frac{\sqrt 3}{2}i\}</math>, so <math>\{1 + \omega, 1 + \zeta\} = \{\frac{1}{2} + \frac{\sqrt 3}{2}i, \frac{1}{2} - \frac{\sqrt 3}{2}i\}</math>. Note that these two numbers are both cube roots of -1, so <math>S = (1 + \omega)^{2007} + (1 + \zeta)^{2007} + (1 + 1)^{2007} = (-1)^{669} + (-1)^{669} + 2^{2007} = 2^{2007} - 2</math>. | ||
+ | |||
+ | Thus, the problem is reduced to calculating <math>2^{2007} - 2 \pmod{1000}</math>. <math>2^{2007} \equiv 0 \pmod{8}</math>, so we need to find <math>2^{2007} \pmod{125}</math> and then use the [[Chinese Remainder Theorem]]. Since <math>\phi (125) = 100</math>, by [[Euler's Totient Theorem]] <math>2^{20 \cdot 100 + 7} \equiv 2^7 \equiv 3 \pmod{125}</math>. Combining, we have <math>2^{2007} \equiv 128 \pmod{1000}</math>, and so <math>3S \equiv 128-2 \pmod{1000} \Rightarrow S\equiv \boxed{042}\pmod{1000}</math>. | ||
+ | |||
+ | ==Solution 2 == | ||
+ | |||
+ | <math>\sum_{k=0}^{n} {n \choose k} =2^n</math>, and <math>\sum_{k=0}^{3n} {3n \choose k} =2^{3n}</math> | ||
+ | |||
+ | <math>\sum_{k=0}^{3n} {3n \choose 3k}=\frac{\sum_{k=0}^{3n} {3n \choose k}+q(n)}{3}</math> where <math>q(n)</math> is an integer <math>-2 \le q(n) \le 2</math> that depends on the value of <math>n</math> and will make the sum an integer. The division by 3 comes from the fact that we're skipping 2 out of every 3 terms in the binomial. So we divide the whole sum by 3 and we add or subtract <math>q(n)</math> to correct for the integer based on the modularity of the sum with 3 | ||
+ | |||
+ | <math>\sum_{k=0}^{3n} {3n \choose 3k}=\frac{2^{3n}+q(n)}{3}</math> | ||
+ | |||
+ | When <math>n</math> is odd, <math>3n</math> is odd, <math>2^{odd} \equiv (-1)^{odd}\;(mod\;3)\equiv -1\;(mod\;3)\equiv 2\;(mod\;3)</math>, Therefore <math>q(n)=-2</math> because we need to subract 2. | ||
+ | |||
+ | When <math>n</math> is even, <math>3n</math> is even, <math>2^{even} \equiv (1)^{even}\;(mod\;3)\equiv 1\;(mod\;3)\equiv -2\;(mod\;3)</math>, Therefore <math>q(n)=2</math> because we need to add 2. | ||
+ | |||
+ | So, the equation becomes: | ||
+ | |||
+ | <math>\sum_{k=0}^{3n} {3n \choose 3k}=\frac{2^{3n}+(-1)^n2}{3}</math> | ||
+ | <math>{2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}=\sum_{k=0}^{3\times 669} { 3\times 669 \choose 3k }=\frac{2^{2007}+(-1)^{669}2}{3}=\frac{2^{2007}-2}{3}</math> | ||
− | <math> | + | <math>2^{2007} \equiv 2^7\;(mod\;1000)\equiv 128\;(mod\;1000)</math> |
+ | <math>2^{2007}-2 \equiv 128-2\;(mod\;1000)\equiv 126\;(mod\;1000)</math> | ||
− | + | <math>\frac{2^{2007}-2}{3} \equiv \frac{126}{3}\;(mod\;1000)\equiv 42\;(mod\;1000)</math> | |
− | <math> | + | Therefore, the remainder when <math>{2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}</math> is divided by 1000 is <math>\boxed{042}</math> |
+ | ~Tomas Diaz. orders@tomasdiaz.com | ||
+ | {{alternate solutions}} | ||
− | {{ | + | == See also == |
− | + | {{Mock AIME box|year=2006-2007|n=4|num-b=9|num-a=11|source=125025}} | |
− | + | [[Category:Intermediate Combinatorics Problems]] | |
− | + | [[Category:Intermediate Number Theory Problems]] | |
− | |||
− | |||
− |
Latest revision as of 12:14, 25 November 2023
Contents
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. The division by 3 comes from the fact that we're skipping 2 out of every 3 terms in the binomial. So we divide the whole sum by 3 and we add or subtract
to correct for the integer based on the modularity of the sum with 3
When is odd,
is odd,
, Therefore
because we need to subract 2.
When is even,
is even,
, Therefore
because we need to add 2.
So, the equation becomes:
Therefore, the remainder when is divided by 1000 is
~Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
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 |