2009 AIME I Problems/Problem 8

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

We can do this in an organized way. $(2^{10}-2^9)+(2^{10}-2^8) ... +(2^{10}-2^0) = (10)2^{10} - 2^9-2^8 ... -2^0$ $(2^9-2^8)+(2^9-2^7) ...+(2^9-2^0) = (9)2^9 - 2^8-2^7 ... -2^0$ $(2^8-2^7)+(2^8-2^6) ...+(2^8-2^0) = (8)2^8-2^7-2^6 ... -2^0$

If we continue doing this, we will have $(10)2^{10}+(9)2^9+(8)2^8 ... +2^1 -2^9-(2)2^8-(3)2^7 ... -(10)2^0$

Which is $(10)2^{10}+(8)2^9+(6)2^8+(4)2^7 ... +(-10)2^0 = \sum_{k = 0}^{10}(10-2k)2^{(10-k)}$

By simplifying this, we will get $(16)2^{10}+2^7-(7)2^4-2$

We only care about the last three digits so the answer will be $384+128-112-2 = 398$

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

2009 AIME I Problems/Problem 8

Problem 8

Solution

See also