Difference between revisions of "2009 AIME I Problems/Problem 8"
m (→Solution 2) |
m (moved extreme bash to bottom) |
||
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: | 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: | ||
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. | This solution can be generalized to apply when <math>10</math> is replaced by other positive integers. | ||
Line 39: | Line 35: | ||
Thus, for <math>n = 10</math>, <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</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. | ||
− | ==Video Solution== | + | ==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)==Video Solution== | ||
https://youtu.be/JIVs2eexmVQ | https://youtu.be/JIVs2eexmVQ | ||
Revision as of 14:02, 16 June 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)==Video Solution== https://youtu.be/JIVs2eexmVQ
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.