Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 10"

(the current start is incorrect, but I can't find any non-brute force way to calculate this ....)
(rv to JBL + try to complete, hope I got the right answer)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
<!--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 the answer is <math>128 - 2 = \boxed{126}</math>.
  
 
== See also ==
 
== See also ==
 
{{Mock AIME box|year=2006-2007|n=4|num-b=9|num-a=11|source=125025}}
 
{{Mock AIME box|year=2006-2007|n=4|num-b=9|num-a=11|source=125025}}
  
−
*[[Binomial theorem]]
+
[[Category:Intermediate Combinatorics Problems]]
−
*[[Modular arithmetic]]
+
[[Category:Intermediate Number Theory Problems]]

Revision as of 14:22, 2 December 2007

Problem

Compute the remainder when

${2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}$

is divided by 1000.

Solution

Let $\omega$ and $\zeta$ be the two complex third-roots of 1. Then let

$S = (1 + \omega)^{2007} + (1 + \zeta)^{2007} + (1 + 1)^{2007} = \sum_{i = 0}^{2007} {2007 \choose i}(\omega^i + \zeta^i + 1)$.

Now, if $i$ is a multiple of 3, $\omega^i + \zeta^i + 1 = 1 + 1 + 1 = 3$. If $i$ is one more than a multiple of 3, $\omega^i + \zeta^i + 1 = \omega + \zeta + 1 = 0$. If $i$ is two more than a multiple of 3, $\omega^i + \zeta^i + 1 = \omega^2 + \zeta^2 + 1= \zeta + \omega + 1 = 0$. Thus

$S = \sum_{i = 0}^{669} 3 {2007 \choose 3i}$, which is exactly three times our desired expression.

We also have an alternative method for calculating $S$: we know that $\{\omega, \zeta\} = \{-\frac{1}{2} + \frac{\sqrt 3}{2}i, -\frac{1}{2} - \frac{\sqrt 3}{2}i\}$, so $\{1 + \omega, 1 + \zeta\} = \{\frac{1}{2} + \frac{\sqrt 3}{2}i, \frac{1}{2} - \frac{\sqrt 3}{2}i\}$. Note that these two numbers are both cube roots of -1, so $S = (1 + \omega)^{2007} + (1 + \zeta)^{2007} + (1 + 1)^{2007} = (-1)^{669} + (-1)^{669} + 2^{2007} = 2^{2007} - 2$.

Thus, the problem is reduced to calculating $2^{2007} - 2 \pmod{1000}$. $2^{2007} \equiv 0 \pmod{8}$, so we need to find $2^{2007} \pmod{125}$ and then use the Chinese Remainder Theorem. Since $\phi (125) = 100$, by Euler's Totient Theorem $2^{20 \cdot 100 + 7} \equiv 2^7 \equiv 3 \pmod{125}$. Combining, we have $2^{2007} \equiv 128 \pmod{1000}$, and so the answer is $128 - 2 = \boxed{126}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_4_2006-2007_Problems/Problem_10&oldid=20525"