Difference between revisions of "2009 AIME I Problems/Problem 8"
(→Solution) |
|||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | |||
− | |||
− | |||
− | |||
− | + | === Solution 1 === | |
− | |||
− | + | 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>. | |
− | <math>(10 | ||
− | + | We can now simply evaluate <math>N\bmod 1000</math>. One reasonably simple way: | |
− | < | + | <cmath> |
+ | \begin{align*} | ||
+ | N | ||
+ | & = 10(2^{10}-1) + 8(2^9 - 2^1) + 6(2^8-2^2) + 4(2^7-2^3) + 2(2^6-2^4) | ||
+ | \ | ||
+ | & = 10(1023) + 8(510) + 6(252) + 4(120) + 2(48) | ||
+ | \ | ||
+ | & = 10(1000+23) + 8(500+10) + 6(250+2) + 480 + 96 | ||
+ | \ | ||
+ | & \equiv (0 + 230) + (0 + 80) + (500 + 12) + 480 + 96 | ||
+ | \ | ||
+ | & \equiv \boxed{398} | ||
+ | \end{align*} | ||
+ | </cmath> | ||
− | We | + | === Solution 2 === |
− | + | ||
− | <math> | + | In this solution we show a more general approach that can be used even if <math>10</math> were replaced by a larger value. |
+ | |||
+ | As in Solution 1, we show that <math>N = \sum_{x=0}^{10} (2x-10) 2^x</math>. | ||
+ | |||
+ | Let <math>A = \sum_{x=0}^{10} x2^x</math> and let <math>B=\sum_{x=0}^{10} 2^x</math>. Then obviously <math>N=2A - 10B</math>. | ||
+ | |||
+ | Computing <math>B</math> is easy, as this is simply a geometric series with sum <math>2^{11}-1 = 2047</math>. Hence <math>B\bmod 1000 = 47</math>. | ||
+ | |||
+ | We can compute <math>A</math> 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 <math>x</math>, write the number <math>2^x</math> into the first <math>x</math> columns. You will get a triangular table. Obviously, the row sums of this table are of the form <math>x2^x</math>, and therefore the sum of all the numbers is precisely <math>A</math>. | ||
+ | |||
+ | Now consider the ten columns in this table. Let's label them 1 to 10. In column <math>x</math>, you have the values <math>2^x</math> to <math>2^{10}</math>, each of them once. And this is just a geometric series with the sum <math>2^{11}-2^x</math>. We can now sum these column sums to get <math>A</math>. | ||
+ | Hence we have <math>A = (2^{11}-2^1) + (2^{11}-2^2) + \cdots + (2^{11}-2^{10})</math>. This simplifies to <math>10\cdot 2^{11} - (2^1 + 2^2 + \cdots + 2^{10}) = 10\cdot 2^{11} - 2^{11} + 2</math>. | ||
+ | |||
+ | Hence <math>A = 10\cdot 2048 - 2048 + 2 \equiv 480 - 48 + 2 = 434 \pmod{1000}</math>. | ||
+ | |||
+ | Then <math>N = 2A - 10B \equiv 2\cdot 434 - 10\cdot 47 = 868 - 470 = \boxed{398}</math>. | ||
== See also == | == See also == | ||
{{AIME box|year=2009|n=I|num-b=7|num-a=9}} | {{AIME box|year=2009|n=I|num-b=7|num-a=9}} |
Revision as of 13:21, 22 March 2009
Contents
[hide]Problem 8
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
Solution 1
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 2
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 .
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 |