Mock AIME 1 Pre 2005 Problems/Problem 11

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

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

Page

Toolbox

Search

Mock AIME 1 Pre 2005 Problems/Problem 11

Problem

Solution

See also