2011 AIME I Problems/Problem 7

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

Let $P(m) = m^x_0 - m^x_1 -m^x_2 - .... - m^x_2011$ . The problem then becomes finding the number of positive integer roots $m$ for which $P(m) = 0$ and $x_0, x_1, ..., x_2011$ are nonnegative integers. We plug in $m = 1$ and see that $P(1) = 1 - 1 - 1... -1 = 1-2011 = -2010$ . Now, we can say that $P(m) = (m-1)Q(m) - 2010$ for some polynomial $Q(m)$ with integer coefficients. Then if $P(m) = 0$ , $(m-1)Q(m) = 2010$ . Thus, it is only possible for $m-1 | 2010$ if $P(m) = 0$ . Now, we need to show that for all $m-1 | 2010$ , $<cmath> m^{x_{0}}=\sum_{k = 1}^{2011}m^{x_{k}}. </cmath>$ . We try with the first few $m$ that satisfy this. For $m = 2$ , we see we can satisfy this if $x_0 = 2010$ , $x_1 = 2009$ , $x_2 = 2008$ , $\cdots$ , $x_2008 = 2$ , $x_2009 = 1$ , $x_2010 = 0$ , $x_2011 = 0$ , because $2^2009 + 2^2008 + \cdots + 2^1 + 2^0 +2^ 0 = 2^2009 + 2^2008 + \cdots + 2^1 + 2^1 = \cdots$ (based on the idea $2^n + 2^n = 2^{n+1}$ , leading to a chain of substitutions of this kind) $= 2^2009 + 2^2008 + 2^2008 = 2^2009 + 2^2009 = '''2^2010'''$ . Thus $2$ is a possible value of $m$ . For other values, for example $m = 3$ , we can use the same strategy, with $x_2011 = x_2010 = x_2009 = 0$ , $x_2008 = x_2007 = 1$ , $x_2006 = x_2005 = 2$ , $\cdots$ , $x_2 = x_1 = 1004$ and $x_0 = 1005$ , because $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 = \cdots$ $=3^1004 +3^1004+3^1004 = '''3^1005'''$ . It's clearly seen we can use the same strategy for all $m-1 |2010$ . We count all positive $m$ satisfying $m-1 |2010$ , and see there are $\boxed{16}$ One notices that $m-1 \mid 2010$ if and only if there exist non-negative integers $x_0,x_1,\ldots,x_{2011}$ such that $m^{x_0} = \sum_{k=1}^{2011}m^{x^k}$ .

Solution 2

To prove the forward case, we proceed by directly finding $x_0,x_1,\ldots,x_{2011}$ . Suppose $m$ is an integer such that $m^{x_0} = \sum_{k=1}^{2011}m^{x^k}$ . We will count how many $x_k = 0$ , how many $x_k = 1$ , etc. Suppose the number of $x_k = 0$ is non-zero. Then, there must be at least $m$ such $x_k$ since $m$ divides all the remaining terms, so $m$ must also divide the sum of all the $m^0$ terms. Thus, if we let $x_k = 0$ for $k = 1,2,\ldots,m$ , we have, $m^{x_0} = m + \sum_{k=m+1}^{2011}m^{x_k}.$ Well clearly, $m^{x_0}$ is greater than $m$ , so $m^2 \mid m^{x_0}$ . $m^2$ will also divide every term, $m^{x_k}$ , where $x_k \geq 2$ . So, all the terms, $m^{x_k}$ , where $x_k < 2$ must sum to a multiple of $m^2$ . If there are exactly $m$ terms where $x_k = 0$ , then we must have at least $m-1$ terms where $x_k = 1$ . Suppose there are exactly $m-1$ such terms and $x_k = 1$ for $k = m+1,m+2,2m-1$ . Now, we have, $m^{x_0} = m^2 + \sum_{k=2m}^{2011}m^{x_k}.$ One can repeat this process for successive powers of $m$ until the number of terms reaches 2011. Since there are $m + j(m-1)$ terms after the $j$ th power, we will only hit exactly 2011 terms if $m-1$ 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 $j = 2010/(m-1) - 1$ (which is an integer since $m-1 \mid 2010$ by assumption, there are exactly 2011 terms. To see that these terms sum to a power of $m$ , 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 $m-1 \mid 2010$ .

Now, for the reverse case, we use the formula $x^k-1 = (x-1)(x^{k-1}+x^{k-2}+\cdots+1).$ Suppose $m^{x_0} = \sum_{k=1}^{2011}m^{x^k}$ has a solution. Subtract 2011 from both sides to get $m^{x_0}-1-2010 = \sum_{k=1}^{2011}(m^{x^k}-1).$ Now apply the formula to get $(m-1)a_0-2010 = \sum_{k=1}^{2011}[(m-1)a_k],$ where $a_k$ are some integers. Rearranging this equation, we find $(m-1)A = 2010,$ where $A = a_0 - \sum_{k=1}^{2011}a_k$ . Thus, if $m$ is a solution, then $m-1 \mid 2010$ .

So, there is one positive integer solution corresponding to each factor of 2010. Since $2010 = 2\cdot 3\cdot 5\cdot 67$ , the number of solutions is $2^4 = \boxed{16}$ .

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

Page

Toolbox

Search

2011 AIME I Problems/Problem 7

Contents

Problem 7

Solution

Solution 2

See also