Difference between revisions of "2009 AIME I Problems/Problem 8"
Thundercloak (talk | contribs) (→Video Solution) |
|||
(13 intermediate revisions by 3 users not shown) | |||
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 1== | + | == Solution 1 (bash) == |
− | |||
− | = | + | 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>. Evaluating <math>N \bmod {1000}</math> yields: |
− | |||
− | |||
− | |||
<cmath> | <cmath> | ||
\begin{align*} | \begin{align*} | ||
Line 25: | Line 21: | ||
</cmath> | </cmath> | ||
− | == Solution | + | == Solution 2 == |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | This solution can be generalized to apply when <math>10</math> is replaced by other positive integers. | |
− | + | 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>. | |
− | + | For <math>n = 10</math>, <math>B = 2^{11}-1 = 2047 \equiv 47 \pmod{1000}</math> by the geometric sequence formula. | |
− | + | <math>2A = \sum_{x=1}^{n+1} (x-1)2^x</math>, so <math>2A - A = 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> | |
− | |||
− | + | <math>434 \pmod{1000}</math>, by the geometric sequence formula and the fact that <math>2^{10} = 1024 \equiv 24 \pmod{1000}</math>. | |
− | + | Thus, for <math>n = 10</math>, <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>. | |
− | ==Solution | + | ==Solution 3== |
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. | ||
− | == | + | ==Solution 4 (Extreme bash)== |
− | + | Find the positive differences in all <math>55</math> pairs and you will get <math>\boxed{398}</math>. | |
+ | (This is not recommended unless you can't find any other solutions to this problem) | ||
== See also == | == See also == |
Latest revision as of 10:12, 16 August 2024
Contents
[hide]Problem
Let . Consider all possible positive differences of pairs of elements of . Let be the sum of all of these differences. Find the remainder when is divided by .
Solution 1 (bash)
When computing , the number will be added times (for terms , , ..., ), and subtracted times. Hence can be computed as . Evaluating yields:
Solution 2
This solution can be generalized to apply when is replaced by other positive integers.
Extending from Solution 2, we get that the sum of all possible differences of pairs of elements in when is equal to . Let , . Then .
For , by the geometric sequence formula.
, so . Hence, for ,
, by the geometric sequence formula and the fact that .
Thus, for , .
Solution 3
Consider the unique differences . Simple casework yields a sum of . This method generalizes nicely as well.
Solution 4 (Extreme bash)
Find the positive differences in all pairs and you will get . (This is not recommended unless you can't find any other solutions to this problem)
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.