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"

m
m (partial solution)
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==
 +
Let <math>\omega</math> and <math>\zeta</math> be the two [[complex]] third-roots of 1.  Then let
  
−
{{solution}}
+
<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} \pmod{1000}</math>.
  
 +
{{solution}}
 
----
 
----
  
Line 12: Line 20:
 
*[[Mock AIME 4 2006-2007 Problems/Problem 9| Previous Problem]]
 
*[[Mock AIME 4 2006-2007 Problems/Problem 9| Previous Problem]]
 
*[[Mock AIME 4 2006-2007 Problems]]
 
*[[Mock AIME 4 2006-2007 Problems]]
 +
* [[Binomial theorem]]
 +
*[[Modular arithmetic]]

Revision as of 16:19, 19 January 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} \pmod{1000}$.

This problem needs a solution. If you have a solution for it, please help us out by adding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_4_2006-2007_Problems/Problem_10&oldid=12234"