2011 AIME I Problems/Problem 7

Revision as of 12:42, 18 May 2011 by Polya78 (talk | contribs) (Proof of sufficiency)

Problem 7

Find the number of positive integers $m$ for which there exist nonnegative integers $x_0$, $x_1$ , $\dots$ , $x_{2011}$ such that \[m^{x_0} = \sum_{k = 1}^{2011} m^{x_k}.\]

Solution

NOTE: This solution is incomplete. Please help make it better.

This formula only works if $m$ is exactly 1 more than a factor of 2010. Since 2010 factors as $2^1 3^1 5^1 67^1$, there are $2^4=\boxed{016}$ such factors.

First I show that $m-1$ must divide $2010$. Consider the desired equation $\pmod{m-1}$. The left side is $\equiv 1$, whereas the right side is $\equiv 2011$. Thus, we have $1 \equiv 2011 \pmod{m-1}$, so $m-1$ must divide 2010.

Now let us prove that any m where m-1 divides 2010 works. Suppose we have such an m. Consider the equation m^k = m^k, for sufficiently large k. Replace m^k on the right hand side by m^(k-1)+m^(k-1)+...m^(k-1), with k terms. We have increased the number of terms by k-1. By repeating this process, we can generate an expression on the rhs with 1+ A(k-1) terms, where A is any positive integer. Since k-1 divides 2010, we can choose A to make the value of 1+A(k-1) equal to 2011.

See also

2011 AIME I (ProblemsAnswer KeyResources)
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