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"

(Undo revision 127150 by Leoouyang (talk))
(Tag: Undo)
Line 2: Line 2:
 
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==
+
==Solutions==
  
−
=== Solution 1 ===
+
===Solution 1===
 +
Find the positive differences in all <math>55</math> pairs and you will get <math>\boxed{398}</math>.
 +
 
 +
=== Solution 2 ===
  
 
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>.
 
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>.
Line 24: Line 27:
 
</cmath>
 
</cmath>
  
−
=== Solution 2 ===
+
=== Solution 3 ===
  
 
In this solution we show a more general approach that can be used even if <math>10</math> were replaced by a larger value.
 
In this solution we show a more general approach that can be used even if <math>10</math> were replaced by a larger value.
Line 45: Line 48:
 
Then <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>.
 
Then <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>.
  
−
===Solution 3===
+
===Solution 4===
 
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>
 
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.
 
<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.

Revision as of 19:11, 19 August 2020

Problem 8

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$.

Solutions

Solution 1

Find the positive differences in all $55$ pairs and you will get $\boxed{398}$.

Solution 2

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$.

We can now simply evaluate $N\bmod 1000$. One reasonably simple way: \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 3

In this solution we show a more general approach that can be used even if $10$ were replaced by a larger value.

As in Solution 1, we show that $N = \sum_{x=0}^{10} (2x-10) 2^x$.

Let $A = \sum_{x=0}^{10} x2^x$ and let $B=\sum_{x=0}^{10} 2^x$. Then obviously $N=2A - 10B$.

Computing $B$ is easy, as this is simply a geometric series with sum $2^{11}-1 = 2047$. Hence $B\bmod 1000 = 47$.

We can compute $A$ using a trick known as the change of summation order.

Imagine writing down a table that has rows with labels 0 to 10. In row $x$, write the number $2^x$ into the first $x$ columns. You will get a triangular table. Obviously, the row sums of this table are of the form $x2^x$, and therefore the sum of all the numbers is precisely $A$.

Now consider the ten columns in this table. Let's label them 1 to 10. In column $x$, you have the values $2^x$ to $2^{10}$, each of them once. And this is just a geometric series with the sum $2^{11}-2^x$. We can now sum these column sums to get $A$. Hence we have $A = (2^{11}-2^1) + (2^{11}-2^2) + \cdots + (2^{11}-2^{10})$. This simplifies to $10\cdot 2^{11} - (2^1 + 2^2 + \cdots + 2^{10}) = 10\cdot 2^{11} - 2^{11} + 2$.

Hence $A = 10\cdot 2048 - 2048 + 2 \equiv 480 - 48 + 2 = 434 \pmod{1000}$.

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

Solution 4

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.

Video Solution

https://youtu.be/JIVs2eexmVQ

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