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

Difference between revisions of "2008 AIME II Problems/Problem 1"

(solution)
 
 
(14 intermediate revisions by 10 users not shown)
Line 2: Line 2:
 
Let <math>N = 100^2 + 99^2 - 98^2 - 97^2 + 96^2 + \cdots + 4^2 + 3^2 - 2^2 - 1^2</math>, where the additions and subtractions alternate in pairs. Find the remainder when <math>N</math> is divided by <math>1000</math>.
 
Let <math>N = 100^2 + 99^2 - 98^2 - 97^2 + 96^2 + \cdots + 4^2 + 3^2 - 2^2 - 1^2</math>, where the additions and subtractions alternate in pairs. Find the remainder when <math>N</math> is divided by <math>1000</math>.
  
−
== Solution ==
+
== Solution 1 ==
 +
Rewriting this sequence with more terms, we have
 +
<center><cmath>\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*}</cmath></center>
 +
Factoring this expression yields
 +
<center><cmath>\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*}</cmath></center>
 +
Next, we get
 +
<center><cmath>\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*}</cmath></center>
 +
Then,
 +
<center><cmath>\begin{align*}
 +
N &= 2\left(\frac{(100)(101)}{2}\right) \mbox{, and simplifying, we get}\\
 +
N &= (100)(101) \mbox{, so}\\
 +
N &= 10100 \mbox{.}
 +
\end{align*}</cmath></center>
 +
Dividing <math>10100</math> by <math>1000</math> yields a remainder of <math>\boxed{100}</math>.
 +
 
 +
== Solution 2 ==
 
Since we want the remainder when <math>N</math> is divided by <math>1000</math>, we may ignore the <math>100^2</math> term. Then, applying the [[difference of squares]] factorization to consecutive terms,
 
Since we want the remainder when <math>N</math> is divided by <math>1000</math>, we may ignore the <math>100^2</math> term. Then, applying the [[difference of squares]] factorization to consecutive terms,
−
<cmath>\begin{align*}
+
<center><cmath>\begin{align*}
 
N &= (99-98)(99+98) - (97-96)(97+96) + (95-94)(95 + 94) + \cdots + (3-2)(3+2) - 1 \\
 
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 \\  
 
&= \underbrace{197 - 193}_4 + \underbrace{189 - 185}_4 + \cdots + \underbrace{5 - 1}_4 \\  
−
&= 4 \cdot \left(\frac{197-5}{8}+1\right) = \boxed{100}.
+
&= 4 \cdot \left(\frac{197-5}{8}+1\right) = \boxed{100}
−
\end{align*}</cmath>
+
\end{align*}</cmath></center>
 +
 
 +
== Solution 3 ==
 +
By observation, we realize that the sequence <cmath>(a+3)^2 + (a+2)^2 - (a+1)^2 - a^2</cmath> alternates every 4 terms. Simplifying, we get <cmath>(a+3)^2 + (a+2)^2 - (a+1)^2 - a^2 = 8a + 12</cmath>, turning <math>N</math> into a arithmetic sequence with 25 terms, them being <math>1, 5, 9, \dots ,97</math>, as the series <math>8a + 12</math> alternates every 4 terms.
 +
 
 +
Applying the sum of arithmetic sequence formula, we get
 +
<center><cmath>\begin{align*}
 +
N &= \frac{25\cdot((8\cdot1 + 12) + (8\cdot97 + 12))}{2} \\
 +
&= \frac{25\cdot(20 + 788)}{2} = 10100
 +
\end{align*}</cmath></center>
 +
So the answer would be <cmath>\frac{10100}{1000} = \boxed{100}</cmath>.
 +
 
 +
 
 +
- erdaifuu
 +
 
 +
==Solution 4==
 +
We can remove the <math>100^2</math> since <math>100^2 \equiv 0 \pmod{1000}</math> and use difference of squares to factor out the rest. This gives <cmath>(1)(99+98) + (-1)(96+97) + ... +(1)(3+2) +(-1)(1+0)</cmath> Writing this another way, we get <cmath>(99(2) - 1) - (97(2)- 1) + (95(2) - 1) -  ... +(3(2)-1) - (1(2) -1)</cmath> We know that the last one is negative because all the numbers before multiplying that are in the form <math>4a - 1</math>(eg. <math>99 = 25(4) - 1 </math>) are positive.
 +
 
 +
Let <math>x = 99</math>. This makes the expression <cmath>(2x-1) - (2(x-2) - 1) + (2(x-4) - 1) - ... + (2(x-96) - 1) -  (2(x-98) - 1)</cmath> This simplifies to <cmath>(2x-1) - (2x-5) + (2x-9) - ... +(2x - 193) - (2x-197)</cmath> Since the first one is positive and the last one is negative, that means there are an even number of terms and using the associative property and the distributive property, all of the <math>2x</math> terms cancel out. A consequence of this is that all of the positive integers turn negative and all the negative ones turn positive(eg. <math>-(2x-5) = -2x + 5</math>).
 +
 
 +
We are left with the sequence <cmath>-1+5-9+...-193+197</cmath> We can notice the property that the number of terms in the sequence to a positive number n is equal to <math>(n+3)/4</math>, as well as the fact that every pair sums up to 4. Therefore the total number of terms is <math>(197+3) / 4 = 50</math>. Therefore, there are 25 pairs each summing up to 4, leaving us with <math>25(4) = \boxed{100}</math>.
 +
 
 +
~idk12345678
 +
==Solution 5==
 +
We simply take the outer pairs and from there, we use the inside terms. That is,
 +
<math>N = 100^2 + 99^2 - 98^2 - 97^2 + 96^2 + \cdots + 4^2 + 3^2 - 2^2 - 1^2</math>
 +
becomes
 +
<math>N = (100^2 - 1^2) + (99^2 - 2^2) - (98^2 - 3^2) - (97^2 - 4^2) + (96^2 - 5^2) ...</math>
 +
and thus is reduced to
 +
<math>N = 101(99 + 97 - 95 - 93 + 81 + 89 - ... - 7 - 5 + 3 + 1)</math>
 +
since the entire sequence has 50 terms. Therefore, the last two terms must be positive as the above inner sequence repeats as follows : Positive - positive - negative - negative.
 +
It follows that <math>N = 101[8(12) + 4] = 101[100]</math>.
 +
So the requested answer is <math>\boxed{100}</math>.
 +
~elpianista227
  
−
== See also ==
+
== See also ==
−
{{AIME box|year=2008|n=II|before=First question|num-a=2}}
+
{{AIME box|year=2008|n=II|before=First Question|num-a=2}}
  
 
[[Category:Intermediate Algebra Problems]]
 
[[Category:Intermediate Algebra Problems]]
 +
{{MAA Notice}}

Latest revision as of 05:02, 14 October 2024

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 1

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\left(\frac{(100)(101)}{2}\right) \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 2

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*}

Solution 3

By observation, we realize that the sequence \[(a+3)^2 + (a+2)^2 - (a+1)^2 - a^2\] alternates every 4 terms. Simplifying, we get \[(a+3)^2 + (a+2)^2 - (a+1)^2 - a^2 = 8a + 12\], turning $N$ into a arithmetic sequence with 25 terms, them being $1, 5, 9, \dots ,97$, as the series $8a + 12$ alternates every 4 terms.

Applying the sum of arithmetic sequence formula, we get

\begin{align*} N &= \frac{25\cdot((8\cdot1 + 12) + (8\cdot97 + 12))}{2} \\ &= \frac{25\cdot(20 + 788)}{2} = 10100 \end{align*}

So the answer would be \[\frac{10100}{1000} = \boxed{100}\].


- erdaifuu

Solution 4

We can remove the $100^2$ since $100^2 \equiv 0 \pmod{1000}$ and use difference of squares to factor out the rest. This gives \[(1)(99+98) + (-1)(96+97) + ... +(1)(3+2) +(-1)(1+0)\] Writing this another way, we get \[(99(2) - 1) - (97(2)- 1) + (95(2) - 1) - ... +(3(2)-1) - (1(2) -1)\] We know that the last one is negative because all the numbers before multiplying that are in the form $4a - 1$(eg. $99 = 25(4) - 1$) are positive.

Let $x = 99$. This makes the expression \[(2x-1) - (2(x-2) - 1) + (2(x-4) - 1) - ... + (2(x-96) - 1) - (2(x-98) - 1)\] This simplifies to \[(2x-1) - (2x-5) + (2x-9) - ... +(2x - 193) - (2x-197)\] Since the first one is positive and the last one is negative, that means there are an even number of terms and using the associative property and the distributive property, all of the $2x$ terms cancel out. A consequence of this is that all of the positive integers turn negative and all the negative ones turn positive(eg. $-(2x-5) = -2x + 5$).

We are left with the sequence \[-1+5-9+...-193+197\] We can notice the property that the number of terms in the sequence to a positive number n is equal to $(n+3)/4$, as well as the fact that every pair sums up to 4. Therefore the total number of terms is $(197+3) / 4 = 50$. Therefore, there are 25 pairs each summing up to 4, leaving us with $25(4) = \boxed{100}$.

~idk12345678

Solution 5

We simply take the outer pairs and from there, we use the inside terms. That is, $N = 100^2 + 99^2 - 98^2 - 97^2 + 96^2 + \cdots + 4^2 + 3^2 - 2^2 - 1^2$ becomes $N = (100^2 - 1^2) + (99^2 - 2^2) - (98^2 - 3^2) - (97^2 - 4^2) + (96^2 - 5^2) ...$ and thus is reduced to $N = 101(99 + 97 - 95 - 93 + 81 + 89 - ... - 7 - 5 + 3 + 1)$ since the entire sequence has 50 terms. Therefore, the last two terms must be positive as the above inner sequence repeats as follows : Positive - positive - negative - negative. It follows that $N = 101[8(12) + 4] = 101[100]$. So the requested answer is $\boxed{100}$. ~elpianista227

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=229792"