AoPSWiki

Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.

Personal tools

Search

Toolbox

Mock AIME 4 2006-2007 Problems/Problem 10

From AoPSWiki

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 the answer is $128 - 2 = \boxed{126}$ .

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 "http://www.artofproblemsolving.com/Wiki/index.php/Mock_AIME_4_2006-2007_Problems/Problem_10"

Categories: Intermediate Combinatorics Problems | Intermediate Number Theory Problems

Want to learn how to tackle those tough MATHCOUNTS and AMC counting and probability problems? Check out Art of Problem Solving's Introduction to Counting & Probability by David Patrick.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us