Difference between revisions of "2009 AIME I Problems/Problem 8"
Line 1: | Line 1: | ||
− | == Problem | + | == Problem == |
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== | |
− | |||
− | |||
Find the positive differences in all <math>55</math> pairs and you will get <math>\boxed{398}</math>. | Find the positive differences in all <math>55</math> pairs and you will get <math>\boxed{398}</math>. | ||
− | + | == Solution 2 == | |
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>. | 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>. | ||
Line 27: | Line 25: | ||
</cmath> | </cmath> | ||
− | + | == Solution 3 == | |
In this solution we show a more general approach that can be used even if <math>10</math> were replaced by a larger value. | In this solution we show a more general approach that can be used even if <math>10</math> were replaced by a larger value. | ||
Line 48: | Line 46: | ||
Then <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>. | Then <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>. | ||
− | + | ==Solution 4== | |
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. |
Revision as of 15:38, 15 February 2021
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
Find the positive differences in all pairs and you will get .
Solution 2
When computing , the number will be added times (for terms , , ..., ), and subtracted times. Hence can be computed as .
We can now simply evaluate . One reasonably simple way:
Solution 3
In this solution we show a more general approach that can be used even if were replaced by a larger value.
As in Solution 1, we show that .
Let and let . Then obviously .
Computing is easy, as this is simply a geometric series with sum . Hence .
We can compute 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 , write the number into the first columns. You will get a triangular table. Obviously, the row sums of this table are of the form , and therefore the sum of all the numbers is precisely .
Now consider the ten columns in this table. Let's label them 1 to 10. In column , you have the values to , each of them once. And this is just a geometric series with the sum . We can now sum these column sums to get . Hence we have . This simplifies to .
Hence .
Then .
Solution 4
Consider the unique differences . Simple casework yields a sum of . This method generalizes nicely as well.
Video Solution
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.