AoPSWiki

Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.

Personal tools

Log in

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 AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.

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