Difference between revisions of "2011 AIME I Problems/Problem 7"
Jonathan.li (talk | contribs) (→Solution 7)) |
Boxtheanswer (talk | contribs) m (→Solution 6 (fast, easy): latexed) |
||
(22 intermediate revisions by 4 users not shown) | |||
Line 4: | Line 4: | ||
==Solution 1== | ==Solution 1== | ||
− | <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_{2010}}</math> equal to <math>1-\left(\frac{1}{m}\right)^x</math> for any power of <math>x</math>. Consider <math>m=2</math>. We can achieve a sum of <math>1-\left(\frac{1}{2}\right)^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 | + | <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_{2010}}</math> equal to <math>1-\left(\frac{1}{m}\right)^x</math> for any power of <math>x</math>. Consider <math>m=2</math>. We can achieve a sum of <math>1-\left(\frac{1}{2}\right)^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 \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>\text{ }\frac{1}{m^{i+1}}</math>s since <math>(m-1)\cdot\frac{1}{m^{i}} = m(m-1)\cdot\frac{1}{m^{i+1}}</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)\text{ }|\text{ } 2010</math> which happens <math>\boxed{016}</math> times. |
==Solution 2== | ==Solution 2== | ||
Let <cmath>P(m) = m^{x_0} - m^{x_1} -m^{x_2} - .... - m^{x_{2011}}</cmath>. 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 <cmath>P(1) = 1 - 1 - 1... -1 = 1-2011 = -2010</cmath> Now, we can say that <cmath>P(m) = (m-1)Q(m) - 2010</cmath> 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 <cmath>P(m) = m^{x_0} - m^{x_1} -m^{x_2} - .... - m^{x_{2011}}</cmath>. 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 <cmath>P(1) = 1 - 1 - 1... -1 = 1-2011 = -2010</cmath> Now, we can say that <cmath>P(m) = (m-1)Q(m) - 2010</cmath> 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 <cmath>m^{x_{0}}=\sum_{k = 1}^{2011}m^{x_{k}}\forall m-1| | + | Now, we need to show that <cmath>m^{x_{0}}=\sum_{k = 1}^{2011}m^{x_{k}}\forall m-1|2010 </cmath> We try with the first few <math>m</math> that satisfy this. |
For <math>m = 2</math>, we see we can satisfy this if <math>x_0 = 2010</math>, <math>x_1 = 2009</math>, <math>x_2 = 2008</math>, <math>\cdots</math> , <math>x_{2008} = 2</math>, <math>x_{2009} = 1</math>, <math> x_{2010} = 0</math>, <math>x_{2011} = 0</math>, because <cmath>2^{2009} + 2^{2008} + \cdots + 2^1 + 2^0 +2^ 0 = 2^{2009} + 2^{2008} + \cdots + 2^1 + 2^1 = \cdots</cmath> (based on the idea <math>2^n + 2^n = 2^{n+1}</math>, leading to a chain of substitutions of this kind) <cmath>= 2^{2009} + 2^{2008} + 2^{2008} = 2^{2009} + 2^{2009} = 2^{2010}</cmath>. Thus <math>2</math> is a possible value of <math>m</math>. For other values, for example <math>m = 3</math>, we can use the same strategy, with <cmath>x_{2011} = x_{2010} = x_{2009} = 0</cmath>, <cmath>x_{2008} = x_{2007} = 1</cmath>, <cmath>x_{2006} = x_{2005} = 2</cmath>, <cmath>\cdots</cmath>, <cmath>x_2 = x_1 = 1004</cmath> and <cmath>x_0 = 1005</cmath>, because | For <math>m = 2</math>, we see we can satisfy this if <math>x_0 = 2010</math>, <math>x_1 = 2009</math>, <math>x_2 = 2008</math>, <math>\cdots</math> , <math>x_{2008} = 2</math>, <math>x_{2009} = 1</math>, <math> x_{2010} = 0</math>, <math>x_{2011} = 0</math>, because <cmath>2^{2009} + 2^{2008} + \cdots + 2^1 + 2^0 +2^ 0 = 2^{2009} + 2^{2008} + \cdots + 2^1 + 2^1 = \cdots</cmath> (based on the idea <math>2^n + 2^n = 2^{n+1}</math>, leading to a chain of substitutions of this kind) <cmath>= 2^{2009} + 2^{2008} + 2^{2008} = 2^{2009} + 2^{2009} = 2^{2010}</cmath>. Thus <math>2</math> is a possible value of <math>m</math>. For other values, for example <math>m = 3</math>, we can use the same strategy, with <cmath>x_{2011} = x_{2010} = x_{2009} = 0</cmath>, <cmath>x_{2008} = x_{2007} = 1</cmath>, <cmath>x_{2006} = x_{2005} = 2</cmath>, <cmath>\cdots</cmath>, <cmath>x_2 = x_1 = 1004</cmath> and <cmath>x_0 = 1005</cmath>, because | ||
<cmath>3^0 + 3^0 + 3^0 +3^1+3^1+3^2+3^2+\cdots+3^{1004} +3^{1004} = 3^1+3^1+3^1+3^2+3^2+\cdots+3^{1004} +3^{1004} = 3^2+3^2+3^2+\cdots+3^{1004} +3^{1004}</cmath> | <cmath>3^0 + 3^0 + 3^0 +3^1+3^1+3^2+3^2+\cdots+3^{1004} +3^{1004} = 3^1+3^1+3^1+3^2+3^2+\cdots+3^{1004} +3^{1004} = 3^2+3^2+3^2+\cdots+3^{1004} +3^{1004}</cmath> | ||
Line 40: | Line 40: | ||
==Solution 6 (fast, easy)== | ==Solution 6 (fast, easy)== | ||
− | The problem is basically saying that we want to find 2011 powers of m that add together to equal another power of m. If we had a power of m, m^n, then to get to m^ | + | The problem is basically saying that we want to find <math>2011</math> powers of <math>m</math> that add together to equal another power of <math>m</math>. If we had a power of <math>m</math>, <math>m^n</math>, then to get to <math>m^{n+1}</math> or <math>m \cdot (m^n)</math>, we have to add <math>m^n</math>, <math> m-1 </math>times. Then when we are at <math>m^{n+1}</math>, to get to <math>m^{n+2}</math>, it is similar. So we have to have <math>m^{\text{some number}} = m^n + (m-1){m^n} + (m-1)(m^{n+1})\dots</math>. This expression has <math>1 + (m-1) + (m-1) + \dots = 1 + k(m-1)</math> terms, and the number of terms must be equal to <math>2011</math> (as stated in the problem). Then <math>1+k(m-1) = 2011</math>, and we get the equation <math>k(m-1) = 2010 = 2\cdot3\cdot5\cdot67</math>. <math>2010</math> has <math>16</math> factors, and setting <math>m-1</math> equal to each of these factors makes <math>\boxed{016}</math> values of <math>m</math>. |
− | ==Solution 7)== | + | |
− | Take | + | ==Solution 7 (xooks-rbo)== |
− | < | + | Take<math>\pmod {m-1}</math> of both sides |
− | 0 \equiv 2010 \ | + | <cmath>m^{x_0} \equiv 1 \pmod {m-1} </cmath> |
− | m-1 | + | <cmath>\sum_{k = 1}^{2011} m^{x_k} \equiv 2011 \pmod {m-1} </cmath> |
− | 2010 has 16 factors, | + | Setting both of these to be congruent to eachother, we get: |
+ | <cmath>1 \equiv 2011 \pmod {m-1} </cmath> | ||
+ | Subtract <math>1</math> from both sides to get: | ||
+ | <cmath>0 \equiv 2010 \pmod {m-1} </cmath> | ||
+ | <math>m-1</math> must be a factor of <math>2010</math>. | ||
+ | |||
+ | <math>2010</math> has <math>16</math> factors, so there are <math>\boxed{16}</math> values of <math>m</math>. | ||
==An Olympiad Problem that's (almost) the exact same (and it came before 2011, MAA)== | ==An Olympiad Problem that's (almost) the exact same (and it came before 2011, MAA)== |
Latest revision as of 20:45, 1 September 2024
Contents
Problem 7
Find the number of positive integers for which there exist nonnegative integers
,
,
,
such that
Solution 1
. 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
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
.
Solution 4 (for noobs like me)
The problem is basically asking how many integers have a power that can be expressed as the sum of 2011 other powers of
(not necessarily distinct). Notice that
,
, and
. Thus, we can safely assume that the equation
must have an integer solution
. To find the number of
-values that allow the aforementioned equation to have an integer solution, we can subtract 1 from the constant
to make the equation equal a friendlier number,
, instead of the ugly prime number
:
. Factor the equation and we get
. The number of values of
that allow
to be an integer is quite obviously the number of factors of
. Factoring
, we obtain
, so the number of positive integers
that satisfy the required condition is
.
-fidgetboss_4000
Solution 5
First of all, note that the nonnegative integer condition really does not matter, since even if we have a nonnegative power, there is always a power of we can multiply to get to non-negative powers. Now we see that our problem is just a matter of m-chopping blocks. What is meant by
-chopping is taking an existing block of say
and turning it into
blocks of
. This process increases the total number of blocks by
per chop.The problem wants us to find the number of positive integers
where some number of chops will turn
block into
such blocks, thus increasing the total amount by
. Thus
, and a cursory check on extreme cases will confirm that there are indeed
possible
s.
Solution 6 (fast, easy)
The problem is basically saying that we want to find powers of
that add together to equal another power of
. If we had a power of
,
, then to get to
or
, we have to add
,
times. Then when we are at
, to get to
, it is similar. So we have to have
. This expression has
terms, and the number of terms must be equal to
(as stated in the problem). Then
, and we get the equation
.
has
factors, and setting
equal to each of these factors makes
values of
.
Solution 7 (xooks-rbo)
Take of both sides
Setting both of these to be congruent to eachother, we get:
Subtract
from both sides to get:
must be a factor of
.
has
factors, so there are
values of
.
An Olympiad Problem that's (almost) the exact same (and it came before 2011, MAA)
https://artofproblemsolving.com/community/c6h84155p486903 2001 Austrian-Polish Math Individual Competition #1 ~MSC
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.