Difference between revisions of "2009 AIME I Problems/Problem 8"

Revision as of 10:32, 23 January 2023

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 (Extreme bash)

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

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

@@ Line 26: / Line 26: @@
 == Solution 3 ==
-This solution is a generalized approach that work when <math>10</math> is replaced by other values.
+This solution can be generalized to apply when <math>10</math> is replaced by other positive integers.
-In similarity to the logic in Solution 2, <math>N = \sum_{x=0}^{10} (2x-10) 2^x</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>.
-Let <math>A = \sum_{x=0}^{10} x2^x</math> and let <math>B=\sum_{x=0}^{10} 2^x</math>. Then <math>N=2A - 10B</math>.
+For <math>n = 10</math>, <math>B = 2^{11}-1 = 2047 \equiv 47 \pmod{1000}</math> by the geometric sequence formula.
-<math>B</math> can be calculated easily by geometric series with sum <math>2^{11}-1 = 2047</math>. Hence <math>B\bmod 1000 = 47</math>.
+<math>2A = \sum_{x=1}^{n+1} (x-1)2^x</math>, so <math>2A - 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>
-We can compute <math>A</math> using a trick known as the change of summation order.
+<math>434 \pmod{1000}</math>, by the geometric sequence formula and the fact that <math>2^{10} = 1024 \equiv 24 \pmod{1000}</math>.
-Imagine writing down a table that has rows with labels 0 to 10. In row <math>x</math>, write the number <math>2^x</math> into the first <math>x</math> columns. You will get a triangular table. Obviously, the row sums of this table are of the form <math>x2^x</math>, and therefore the sum of all the numbers is precisely <math>A</math>.
+Thus, for <math>n = 10</math>, <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>.
-Now consider the ten columns in this table. Let's label them 1 to 10. In column <math>x</math>, you have the values <math>2^x</math> to <math>2^{10}</math>, each of them once. And this is just a geometric series with the sum <math>2^{11}-2^x</math>. We can now sum these column sums to get <math>A</math>.
-Hence we have <math>A = (2^{11}-2^1) + (2^{11}-2^2) + \cdots + (2^{11}-2^{10})</math>. This simplifies to <math>10\cdot 2^{11} - (2^1 + 2^2 + \cdots + 2^{10}) = 10\cdot 2^{11} - 2^{11} + 2</math>.
-Hence <math>A = 10\cdot 2048 - 2048 + 2 \equiv 480 - 48 + 2 = 434 \pmod{1000}</math>.
-Then <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>.
 ==Solution 4==

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

Page

Toolbox

Search