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"

(→‎Solution 2)
Line 28: Line 28:
 
<math>\sum_{k=0}^{n} {n \choose k} =2^n</math>, and <math>\sum_{k=0}^{3n} {3n \choose 3k} =2^{3n}</math>
 
<math>\sum_{k=0}^{n} {n \choose k} =2^n</math>, and <math>\sum_{k=0}^{3n} {3n \choose 3k} =2^{3n}</math>
  
−
<math>\sum_{k=0}^{3n} \begin{pmatrix} 3n \\ 3k \end{pmatrix}=\frac{\sum_{k=0}^{3n} \begin{pmatrix} 3n \\ k \end{pmatrix}+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.
+
<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.
  
−
<math>\sum_{k=0}^{3n} \begin{pmatrix} 3n \\ 3k \end{pmatrix}=\frac{2^{3n}+q(n)}{3}</math>  
+
<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)</math>, Therefore <math>q(n)=-2</math>
 
When <math>n</math> is odd, <math>3n</math> is odd, <math>2^{odd} \equiv (-1)^{odd}\;(mod\;3)\equiv -1\;(mod\;3)</math>, Therefore <math>q(n)=-2</math>
Line 38: Line 38:
 
So the equation becomes:
 
So the equation becomes:
  
−
<math>\sum_{k=0}^{3n} \begin{pmatrix} 3n \\ 3k \end{pmatrix}=\frac{2^{3n}+(-1)^n2}{3}</math>  
+
<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} \begin{pmatrix} 3\times 669 \\ 3k \end{pmatrix}=\frac{2^{2007}+(-1)^{669}2}{3}=\frac{2^{2007}-2}{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>
  
 
== See also ==
 
== See also ==

Revision as of 12:02, 25 November 2023

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 $3S \equiv 128-2 \pmod{1000} \Rightarrow S\equiv \boxed{042}\pmod{1000}$.

Solution 2

$\sum_{k=0}^{n} {n \choose k} =2^n$, and $\sum_{k=0}^{3n} {3n \choose 3k} =2^{3n}$

$\sum_{k=0}^{3n} {3n \choose 3k}=\frac{\sum_{k=0}^{3n} {3n \choose k}+q(n)}{3}$ where $q(n)$ is an integer $-2 \le q(n) \le 2$ that depends on the value of $n$ and will make the sum an integer.

$\sum_{k=0}^{3n} {3n \choose 3k}=\frac{2^{3n}+q(n)}{3}$

When $n$ is odd, $3n$ is odd, $2^{odd} \equiv (-1)^{odd}\;(mod\;3)\equiv -1\;(mod\;3)$, Therefore $q(n)=-2$

When $n$ is even, $3n$ is even, $2^{even} \equiv (1)^{even}\;(mod\;3)\equiv 1\;(mod\;3)$, Therefore $q(n)=2$

So the equation becomes:

$\sum_{k=0}^{3n} {3n \choose 3k}=\frac{2^{3n}+(-1)^n2}{3}$

${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}$

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=205719"