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 "2009 AIME I Problems/Problem 8"

(→‎Solution)
(→‎Video Solution)
 
(22 intermediate revisions by 10 users not shown)
Line 1: Line 1:
−
== Problem 8 ==
+
== Problem ==
 
Let <math>S = \{2^0,2^1,2^2,\ldots,2^{10}\}</math>. Consider all possible positive differences of pairs of elements of <math>S</math>. Let <math>N</math> be the sum of all of these differences. Find the remainder when <math>N</math> is divided by <math>1000</math>.
 
Let <math>S = \{2^0,2^1,2^2,\ldots,2^{10}\}</math>. Consider all possible positive differences of pairs of elements of <math>S</math>. Let <math>N</math> be the sum of all of these differences. Find the remainder when <math>N</math> is divided by <math>1000</math>.
  
−
==Solution==
+
== Solution 1 (bash) ==
−
We can do this in an organized way.
 
−
<math> (2^{10}-2^9)+(2^{10}-2^8) ... +(2^{10}-2^0) = (10)2^{10} - 2^9-2^8 ... -2^0</math>
 
−
<math> (2^9-2^8)+(2^9-2^7) ...+(2^9-2^0) = (9)2^9 - 2^8-2^7 ... -2^0</math>
 
−
<math>(2^8-2^7)+(2^8-2^6) ...+(2^8-2^0) = (8)2^8-2^7-2^6 ... -2^0</math>
 
  
−
If we continue doing this, we will have
+
When computing <math>N</math>, the number <math>2^x</math> will be added <math>x</math> times (for terms <math>2^x-2^0</math>, <math>2^x-2^1</math>, ..., <math>2^x - 2^{x-1}</math>), and subtracted <math>10-x</math> times. Hence <math>N</math> can be computed as <math>N=10\cdot 2^{10} + 8\cdot 2^9 + 6\cdot 2^8 + \cdots - 8\cdot 2^1 - 10\cdot 2^0</math>. Evaluating <math>N \bmod {1000}</math> yields:
−
<math>(10)2^{10}+(9)2^9+(8)2^8 ... +2^1 -2^9-(2)2^8-(3)2^7 ... -(10)2^0</math>
 
  
−
Which is
+
<cmath>
−
<math>(10)2^{10}+(8)2^9+(6)2^8+(4)2^7 ... +(-10)2^0 = \sum_{k = 0}^{10}(10-2k)2^{(10-k)}</math>
+
\begin{align*}
 +
N
 +
& = 10(2^{10}-1) + 8(2^9 - 2^1) + 6(2^8-2^2) + 4(2^7-2^3) + 2(2^6-2^4)
 +
\\
 +
& = 10(1023) + 8(510) + 6(252) + 4(120) + 2(48)
 +
\\
 +
& = 10(1000+23) + 8(500+10) + 6(250+2) + 480 + 96
 +
\\
 +
& \equiv (0 + 230) + (0 + 80) + (500 + 12) + 480 + 96
 +
\\
 +
& \equiv \boxed{398}
 +
\end{align*}
 +
</cmath>
  
−
By simplifying this, we will get
+
== Solution 2 ==
−
<math>(16)2^{10}+2^7-(7)2^4-2</math>
 
  
−
We only care about the last three digits
+
This solution can be generalized to apply when <math>10</math> is replaced by other positive integers.
−
so the answer will be
+
 
−
<math>384+128-112-2 = 398</math>
+
Extending from Solution 2, we get that the sum <math>N</math> of all possible differences of pairs of elements in <math>S</math> when <math>S = \{2^0,2^1,2^2,\ldots,2^{n}\}</math> is equal to <math>\sum_{x=0}^{n} (2x-n) 2^x</math>. Let <math>A = \sum_{x=0}^{n} x2^x</math>, <math>B=\sum_{x=0}^{n} 2^x</math>. Then <math>N=2A - nB</math>.
 +
 
 +
For <math>n = 10</math>, <math>B = 2^{11}-1 = 2047 \equiv 47 \pmod{1000}</math> by the geometric sequence formula.
 +
 
 +
<math>2A = \sum_{x=1}^{n+1} (x-1)2^x</math>, so <math>2A - A = A = n2^{n+1} - \sum_{x=1}^{n} 2^x</math>. Hence, for <math>n = 10</math>, <math>A = 10 \cdot 2^{11} - 2^{11} + 2 = 9 \cdot 2^{11} + 2 \equiv 48 \cdot 9 + 2 =</math>
 +
 
 +
<math>434 \pmod{1000}</math>, by the geometric sequence formula and the fact that <math>2^{10} = 1024 \equiv 24 \pmod{1000}</math>.
 +
 
 +
Thus, for <math>n = 10</math>, <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>.
 +
 
 +
==Solution 3==
 +
Consider the unique differences <math>2^{a + n} - 2^a</math>. Simple casework yields a sum of <math>\sum_{n = 1}^{10}(2^n - 1)(2^{11 - n} - 1) = \sum_{n = 1}^{10}2^{11} + 1 - 2^n - 2^{11 - n} = 10\cdot2^{11} + 10 - 2(2 + 2^2 + \cdots + 2^{10})</math>
 +
<math>= 10\cdot2^{11} + 10 - 2^2(2^{10} - 1)\equiv480 + 10 - 4\cdot23\equiv\boxed{398}\pmod{1000}</math>. This method generalizes nicely as well.
 +
 
 +
==Solution 4 (Extreme bash)==
 +
Find the positive differences in all <math>55</math> pairs and you will get <math>\boxed{398}</math>.
 +
(This is not recommended unless you can't find any other solutions to this problem)
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2009|n=I|num-b=7|num-a=9}}
 
{{AIME box|year=2009|n=I|num-b=7|num-a=9}}
 +
[[Category:Intermediate Number Theory Problems]]
 +
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 10:12, 16 August 2024

Problem

Let $S = \{2^0,2^1,2^2,\ldots,2^{10}\}$. Consider all possible positive differences of pairs of elements of $S$. Let $N$ be the sum of all of these differences. Find the remainder when $N$ is divided by $1000$.

Solution 1 (bash)

When computing $N$, the number $2^x$ will be added $x$ times (for terms $2^x-2^0$, $2^x-2^1$, ..., $2^x - 2^{x-1}$), and subtracted $10-x$ times. Hence $N$ can be computed as $N=10\cdot 2^{10} + 8\cdot 2^9 + 6\cdot 2^8 + \cdots - 8\cdot 2^1 - 10\cdot 2^0$. Evaluating $N \bmod {1000}$ yields:

\begin{align*} N & = 10(2^{10}-1) + 8(2^9 - 2^1) + 6(2^8-2^2) + 4(2^7-2^3) + 2(2^6-2^4) \\ & = 10(1023) + 8(510) + 6(252) + 4(120) + 2(48) \\ & = 10(1000+23) + 8(500+10) + 6(250+2) + 480 + 96 \\ & \equiv (0 + 230) + (0 + 80) + (500 + 12) + 480 + 96 \\ & \equiv \boxed{398} \end{align*}

Solution 2

This solution can be generalized to apply when $10$ is replaced by other positive integers.

Extending from Solution 2, we get that the sum $N$ of all possible differences of pairs of elements in $S$ when $S = \{2^0,2^1,2^2,\ldots,2^{n}\}$ is equal to $\sum_{x=0}^{n} (2x-n) 2^x$. Let $A = \sum_{x=0}^{n} x2^x$, $B=\sum_{x=0}^{n} 2^x$. Then $N=2A - nB$.

For $n = 10$, $B = 2^{11}-1 = 2047 \equiv 47 \pmod{1000}$ by the geometric sequence formula.

$2A = \sum_{x=1}^{n+1} (x-1)2^x$, so $2A - A = A = n2^{n+1} - \sum_{x=1}^{n} 2^x$. Hence, for $n = 10$, $A = 10 \cdot 2^{11} - 2^{11} + 2 = 9 \cdot 2^{11} + 2 \equiv 48 \cdot 9 + 2 =$

$434 \pmod{1000}$, by the geometric sequence formula and the fact that $2^{10} = 1024 \equiv 24 \pmod{1000}$.

Thus, for $n = 10$, $N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}$.

Solution 3

Consider the unique differences $2^{a + n} - 2^a$. Simple casework yields a sum of $\sum_{n = 1}^{10}(2^n - 1)(2^{11 - n} - 1) = \sum_{n = 1}^{10}2^{11} + 1 - 2^n - 2^{11 - n} = 10\cdot2^{11} + 10 - 2(2 + 2^2 + \cdots + 2^{10})$ $= 10\cdot2^{11} + 10 - 2^2(2^{10} - 1)\equiv480 + 10 - 4\cdot23\equiv\boxed{398}\pmod{1000}$. This method generalizes nicely as well.

Solution 4 (Extreme bash)

Find the positive differences in all $55$ pairs and you will get $\boxed{398}$. (This is not recommended unless you can't find any other solutions to this problem)

See also

2009 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 7 		Followed by
Problem 9
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=2009_AIME_I_Problems/Problem_8&oldid=225127"