Difference between revisions of "Mock AIME 1 Pre 2005 Problems/Problem 11"

(added solution)
 
Line 7: Line 7:
 
Consider the polynomial <cmath>f(x)=(x-1)^{2004}=\sum_{n=0}^{2004}\binom{2004}{n}\cdot(-1)^n x^{2004-n}.</cmath>
 
Consider the polynomial <cmath>f(x)=(x-1)^{2004}=\sum_{n=0}^{2004}\binom{2004}{n}\cdot(-1)^n x^{2004-n}.</cmath>
  
Let <math>\omega^3=1</math> with <math>\omega\neq 1</math>. We have <math>\begin{align*}
+
Let <math>\omega^3=1</math> with <math>\omega\neq 1</math>. We have  
\frac{f(1)+f(\omega)+f(\omega^2)}{3}
+
 
 +
\begin{align*}
 +
\frac{f(1)+f(\omega)+f(\omega^2)}{3} \\
 
&= \frac{(1-1)^{2004}+(\omega-1)^{2004}+(\omega^2-1)^{2004}}{3} \\
 
&= \frac{(1-1)^{2004}+(\omega-1)^{2004}+(\omega^2-1)^{2004}}{3} \\
 
&= \frac{1}{3}\sum_{n=0}^{2004}\binom{2004}{n}\cdot(-1)^n\cdot(1^{2004-n}+\omega^{2004-n}+(\omega^2)^{2004-n}) \\
 
&= \frac{1}{3}\sum_{n=0}^{2004}\binom{2004}{n}\cdot(-1)^n\cdot(1^{2004-n}+\omega^{2004-n}+(\omega^2)^{2004-n}) \\
&= \sum_{n=0}^{668}(-1)^n \binom{2004}{3n}</math>
+
&= \sum_{n=0}^{668}(-1)^n \binom{2004}{3n}
 +
\end{align*}
  
 
where the last step follows because <math>1^k+\omega^k+\omega^{2k}</math> is 0 when <math>k</math> is not divisible by 3, and <math>3</math> when <math>k</math> is divisible by 3.
 
where the last step follows because <math>1^k+\omega^k+\omega^{2k}</math> is 0 when <math>k</math> is not divisible by 3, and <math>3</math> when <math>k</math> is divisible by 3.

Revision as of 10:46, 2 July 2015

Problem

Let $S$ denote the value of the sum \[\sum_{n=0}^{668} (-1)^{n} {2004 \choose 3n}\] Determine the remainder obtained when $S$ is divided by $1000$.

Solution

Consider the polynomial \[f(x)=(x-1)^{2004}=\sum_{n=0}^{2004}\binom{2004}{n}\cdot(-1)^n x^{2004-n}.\]

Let $\omega^3=1$ with $\omega\neq 1$. We have

\begin{align*} \frac{f(1)+f(\omega)+f(\omega^2)}{3} \\ &= \frac{(1-1)^{2004}+(\omega-1)^{2004}+(\omega^2-1)^{2004}}{3} \\ &= \frac{1}{3}\sum_{n=0}^{2004}\binom{2004}{n}\cdot(-1)^n\cdot(1^{2004-n}+\omega^{2004-n}+(\omega^2)^{2004-n}) \\ &= \sum_{n=0}^{668}(-1)^n \binom{2004}{3n} \end{align*}

where the last step follows because $1^k+\omega^k+\omega^{2k}$ is 0 when $k$ is not divisible by 3, and $3$ when $k$ is divisible by 3.

We now compute $\frac{(1-1)^{2004}+(\omega-1)^{2004}+(\omega^2-1)^{2004}}{3}$. WLOG, let $\omega = \frac{-1+\sqrt{3}i}{2}, \omega^2=\frac{-1-\sqrt{3}i}{2}$. Then $\omega-1=\frac{-3+\sqrt{3}i}{2} = \sqrt{3}\cdot \frac{-\sqrt{3}+i}{2}$, and $\omega^2-1=\sqrt{3}\cdot\frac{-\sqrt{3}-i}{2}$. These numbers are both of the form $\sqrt{3}\cdot\varphi$, where $\varphi$ is a 12th root of unity, so both of these, when raised to the 2004-th power, become $3^{1002}$. Thus, our desired sum becomes $2\cdot3^{1001}$.

To find $2\cdot3^{1001} \pmod{1000}$, we notice that $3^{\phi{500}}\equiv 3^{200}\equiv 1 \pmod{500}$ so that $3^{1001}\equiv 3 \pmod{500}$. Then $2\cdot3^{1001}=2(500k+3)=1000k+6$. Thus, our answer is $\boxed{006}$.

See also

Mock AIME 1 Pre 2005 (Problems, Source)
Preceded by
Problem 10
Followed by
Problem 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15