Art of Problem Solving
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

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

Newer edit →
added solution
 
No edit summary
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 09: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
Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=Mock_AIME_1_Pre_2005_Problems/Problem_11&oldid=70959"