Difference between revisions of "2011 AIME I Problems/Problem 7"
m (→Solution 3) |
m (→Solution 2) |
||
Line 6: | Line 6: | ||
<math> m^{x_0}= m^{x_1} +m^{x_2} + .... + m^{x_{2011}}</math>. Now, divide by <math>m^{x_0}</math> to get <math>1= m^{x_1-x_0} +m^{x_2-x_0} + .... + m^{x_{2011}-x_0}</math>. Notice that since we can choose all nonnegative <math>x_0,...,x_{2011}</math>, we can make <math>x_n-x_0</math> whatever we desire. WLOG, let <math>x_0\geq...\geq x_{2011}</math> and let <math>a_n=x_n-x_0</math>. Notice that, also, <math>m^{a_{2011}}</math> doesn't matter if we are able to make <math> m^{a_1} +m^{a_2} + .... + m^{a_2011}</math> equal to <math>1-(\frac{1}{m})^x</math> for any power of <math>x</math>. Consider <math>m=2</math>. We can achieve a sum of <math>1-(\frac{1}{2})^x</math> by doing <math>\frac{1}{2}+\frac{1}{4}+...</math> (the simplest" sequence). If we don't have <math>\frac{1}{2}</math>, to compensate, we need <math>2\cdot 1\frac{1}{4}</math>'s. Now, let's try to generalize. The "simplest" sequence is having <math>\frac{1}{m}</math> <math>m-1</math> times, <math>\frac{1}{m^2}</math> <math>m-1</math> times, <math>\ldots</math>. To make other sequences, we can split <math>m-1</math> <math>\frac{1}{m^i}</math>s into <math>m(m-1)</math> <math>\frac{1}{m^{i+1}}</math>s since <math>m\cdot\frac{1}{m^{i+1}}\cdot =m(m-1)\cdot\frac{1}{m^{i}}</math>. Since we want <math>2010</math> terms, we have <math>\sum</math> <math>(m-1)\cdot m^x=2010</math>. However, since we can set <math>x</math> to be anything we want (including 0), all we care about is that <math>m-1 | 2010</math> which happens <math>\boxed{016}</math> times. | <math> m^{x_0}= m^{x_1} +m^{x_2} + .... + m^{x_{2011}}</math>. Now, divide by <math>m^{x_0}</math> to get <math>1= m^{x_1-x_0} +m^{x_2-x_0} + .... + m^{x_{2011}-x_0}</math>. Notice that since we can choose all nonnegative <math>x_0,...,x_{2011}</math>, we can make <math>x_n-x_0</math> whatever we desire. WLOG, let <math>x_0\geq...\geq x_{2011}</math> and let <math>a_n=x_n-x_0</math>. Notice that, also, <math>m^{a_{2011}}</math> doesn't matter if we are able to make <math> m^{a_1} +m^{a_2} + .... + m^{a_2011}</math> equal to <math>1-(\frac{1}{m})^x</math> for any power of <math>x</math>. Consider <math>m=2</math>. We can achieve a sum of <math>1-(\frac{1}{2})^x</math> by doing <math>\frac{1}{2}+\frac{1}{4}+...</math> (the simplest" sequence). If we don't have <math>\frac{1}{2}</math>, to compensate, we need <math>2\cdot 1\frac{1}{4}</math>'s. Now, let's try to generalize. The "simplest" sequence is having <math>\frac{1}{m}</math> <math>m-1</math> times, <math>\frac{1}{m^2}</math> <math>m-1</math> times, <math>\ldots</math>. To make other sequences, we can split <math>m-1</math> <math>\frac{1}{m^i}</math>s into <math>m(m-1)</math> <math>\frac{1}{m^{i+1}}</math>s since <math>m\cdot\frac{1}{m^{i+1}}\cdot =m(m-1)\cdot\frac{1}{m^{i}}</math>. Since we want <math>2010</math> terms, we have <math>\sum</math> <math>(m-1)\cdot m^x=2010</math>. However, since we can set <math>x</math> to be anything we want (including 0), all we care about is that <math>m-1 | 2010</math> which happens <math>\boxed{016}</math> times. | ||
− | ==Solution | + | ==Solution 2== |
Let <math>P(m) = m^{x_0} - m^{x_1} -m^{x_2} - .... - m^{x_{2011}}</math>. The problem then becomes finding the number of positive integer roots <math>m</math> for which <math>P(m) = 0</math> and <math>x_0, x_1, ..., x_{2011}</math> are nonnegative integers. We plug in <math>m = 1</math> and see that <math>P(1) = 1 - 1 - 1... -1 = 1-2011 = -2010</math>. Now, we can say that <math>P(m) = (m-1)Q(m) - 2010</math> for some polynomial <math>Q(m)</math> with integer coefficients. Then if <math>P(m) = 0</math>, <math>(m-1)Q(m) = 2010</math>. Thus, if <math>P(m) = 0</math>, then <math>m-1 | 2010</math> . | Let <math>P(m) = m^{x_0} - m^{x_1} -m^{x_2} - .... - m^{x_{2011}}</math>. The problem then becomes finding the number of positive integer roots <math>m</math> for which <math>P(m) = 0</math> and <math>x_0, x_1, ..., x_{2011}</math> are nonnegative integers. We plug in <math>m = 1</math> and see that <math>P(1) = 1 - 1 - 1... -1 = 1-2011 = -2010</math>. Now, we can say that <math>P(m) = (m-1)Q(m) - 2010</math> for some polynomial <math>Q(m)</math> with integer coefficients. Then if <math>P(m) = 0</math>, <math>(m-1)Q(m) = 2010</math>. Thus, if <math>P(m) = 0</math>, then <math>m-1 | 2010</math> . | ||
Now, we need to show that for all <math>m-1 | 2010</math>, <math> m^{x_{0}}=\sum_{k = 1}^{2011}m^{x_{k}}. </math>. We try with the first few <math>m</math> that satisfy this. | Now, we need to show that for all <math>m-1 | 2010</math>, <math> m^{x_{0}}=\sum_{k = 1}^{2011}m^{x_{k}}. </math>. We try with the first few <math>m</math> that satisfy this. |
Revision as of 17:08, 18 February 2016
Problem 7
Find the number of positive integers for which there exist nonnegative integers , , , such that
Solution
. Now, divide by to get . Notice that since we can choose all nonnegative , we can make whatever we desire. WLOG, let and let . Notice that, also, doesn't matter if we are able to make equal to for any power of . Consider . We can achieve a sum of by doing (the simplest" sequence). If we don't have , to compensate, we need 's. Now, let's try to generalize. The "simplest" sequence is having times, times, . To make other sequences, we can split s into s since . Since we want terms, we have . However, since we can set to be anything we want (including 0), all we care about is that which happens times.
Solution 2
Let . The problem then becomes finding the number of positive integer roots for which and are nonnegative integers. We plug in and see that . Now, we can say that for some polynomial with integer coefficients. Then if , . Thus, if , then . Now, we need to show that for all , . We try with the first few that satisfy this. For , we see we can satisfy this if , , , , , , , , because (based on the idea , leading to a chain of substitutions of this kind) . Thus is a possible value of . For other values, for example , we can use the same strategy, with , , , , and , because . It's clearly seen we can use the same strategy for all . We count all positive satisfying , and see there are
Solution 3
One notices that if and only if there exist non-negative integers such that .
To prove the forward case, we proceed by directly finding . Suppose is an integer such that . We will count how many , how many , etc. Suppose the number of is non-zero. Then, there must be at least such since divides all the remaining terms, so must also divide the sum of all the terms. Thus, if we let for , we have, Well clearly, is greater than , so . will also divide every term, , where . So, all the terms, , where must sum to a multiple of . If there are exactly terms where , then we must have at least terms where . Suppose there are exactly such terms and for . Now, we have, One can repeat this process for successive powers of until the number of terms reaches 2011. Since there are terms after the th power, we will only hit exactly 2011 terms if is a factor of 2010. To see this, Thus, when (which is an integer since by assumption, there are exactly 2011 terms. To see that these terms sum to a power of , we realize that the sum is a geometric series: Thus, we have found a solution for the case .
Now, for the reverse case, we use the formula Suppose has a solution. Subtract 2011 from both sides to get Now apply the formula to get where are some integers. Rearranging this equation, we find where . Thus, if is a solution, then .
So, there is one positive integer solution corresponding to each factor of 2010. Since , the number of solutions is .
See also
2011 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
- AIME Problems and Solutions
- American Invitational Mathematics Examination
- Mathematics competition resources
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.