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

2008 AIME II Problems/Problem 1

Revision as of 00:38, 13 July 2016 by Niyu (talk | contribs) (→‎Solution 2)

Problem

Let $N = 100^2 + 99^2 - 98^2 - 97^2 + 96^2 + \cdots + 4^2 + 3^2 - 2^2 - 1^2$, where the additions and subtractions alternate in pairs. Find the remainder when $N$ is divided by $1000$.

Solution

Rewriting this sequence with more terms, we have

\begin{align*} N &= 100^2 + 99^2 - 98^2 - 97^2 + 96^2 + 95^2 - 94^2 - 93^2 + 92^2 + 91^2 + \ldots - 10^2 - 9^2 + 8^2 + 7^2 - 6^2 - 5^2 + 4^2 + 3^2 - 2^2 - 1^2 \mbox{, and reordering, we get}\\ N &= (100^2 - 98^2) + (99^2 - 97^2) + (96^2 - 94^2) + (95^2 - 93^2) + (92^2 - 90^2) + \ldots + (8^2 - 6^2) + (7^2 - 5^2) +(4^2 - 2^2) + (3^2 - 1^2) \mbox{.} \end{align*}

Factoring this expression yields

\begin{align*} N &= (100 - 98)(100 + 98) + (99 - 97)(99 + 97) + (96 - 94)(96 + 94) + (95 - 93)(95 + 93) + (92 - 90)(90 + 92) + \ldots + (8 - 6)(8 + 6) + (7 - 5)(7 + 5) + (4 - 2)(4 + 2) + (3 - 1)(3 + 1) \mbox{, leading to}\\ N &= 2(100 + 98) + 2(99 + 97) + 2(96 + 94) + 2(95 + 93) + 2(92 + 90) + \ldots + 2(8 + 6) + 2(7 + 5) + 2(4 + 2) + 2(3 + 1) \mbox{.} \end{align*}

Next, we get

\begin{align*} N &= 2(100 + 98 + 99 + 97 + 96 + 94 + 95 + 93 + 92 + 90 + \ldots + 8 + 6 + 7 + 5 + 4 + 2 + 3 + 1 \mbox{, and rearranging terms yields}\\ N &= 2(100 + 99 + 98 + 97 + 96 + \ldots + 5 + 4 + 3 + 2 + 1) \mbox{.} \end{align*}

Then,

\begin{align*} N &= 2(\frac{(100)(101)}{2} \mbox{, and simplifying, we get}\\ N &= (100)(101) \mbox{, so}\\ N &= 10100 \mbox{.} \end{align*}

Dividing $10100$ by $1000$ yields a remainder of $\boxed{100}$.

Solution

Since we want the remainder when $N$ is divided by $1000$, we may ignore the $100^2$ term. Then, applying the difference of squares factorization to consecutive terms,

\begin{align*} N &= (99-98)(99+98) - (97-96)(97+96) + (95-94)(95 + 94) + \cdots + (3-2)(3+2) - 1 \\ &= \underbrace{197 - 193}_4 + \underbrace{189 - 185}_4 + \cdots + \underbrace{5 - 1}_4 \\ &= 4 \cdot \left(\frac{197-5}{8}+1\right) = \boxed{100} \end{align*}

See also

2008 AIME II (Problems • Answer Key • Resources)
Preceded by
First Question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_AIME_II_Problems/Problem_1&oldid=79290"