2009 AIME I Problems/Problem 8

Revision as of 17:19, 20 March 2009 by Ewcikewqikd (talk | contribs) (New page: == Problem 8 == 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 ...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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$