2011 AIME I Problems/Problem 7
Contents
Problem 7
Find the number of positive integers for which there exist nonnegative integers
,
,
,
such that
Solution
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, it is only possible for
if
.
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
One notices that
if and only if there exist non-negative integers
such that
.
Solution 2
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,
\[m+j(m-1) = 2011 \Rightarrow m-1+j(m-1) &= 2010 \Rightarrow (m-1)(j+1) = 2010.\] (Error compiling LaTeX. Unknown error_msg)
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:
\[1 + (m-1) + (m-1)m+(m-1)m^2 + \cdots + (m-1)m^j &= 1+(m-1)\frac{m^{j+1}-1}{m-1} = m^{j+1}.\] (Error compiling LaTeX. Unknown error_msg)
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 |