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

Revision as of 13:21, 22 March 2009

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

Solution

Solution 1

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 2

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

@@ Line 3: / Line 3: @@
 ==Solution==
-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
+=== Solution 1 ===
-<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
+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>.
-<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>
-By simplifying this, we will get
+We can now simply evaluate <math>N\bmod 1000</math>. One reasonably simple way:
-<math>(16)2^{10}+2^7-(7)2^4-2</math>
+<cmath>
+\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>
-We only care about the last three digits
+=== Solution 2 ===
-so the answer will be
-<math>384+128-112-2 = \boxed {398}</math>
+In this solution we show a more general approach that can be used even if <math>10</math> were replaced by a larger value.
+As in Solution 1, we show that <math>N = \sum_{x=0}^{10} (2x-10) 2^x</math>.
+Let <math>A = \sum_{x=0}^{10} x2^x</math> and let <math>B=\sum_{x=0}^{10} 2^x</math>. Then obviously <math>N=2A - 10B</math>.
+Computing <math>B</math> is easy, as this is simply a geometric series with sum <math>2^{11}-1 = 2047</math>. Hence <math>B\bmod 1000 = 47</math>.
+We can compute <math>A</math> 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 <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>.
+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>.
 == See also ==
 {{AIME box|year=2009|n=I|num-b=7|num-a=9}}

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