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 1

$m^{x_0}= m^{x_1} +m^{x_2} + .... + m^{x_{2011}}$ . Now, divide by $m^{x_0}$ to get $1= m^{x_1-x_0} +m^{x_2-x_0} + .... + m^{x_{2011}-x_0}$ . Notice that since we can choose all nonnegative $x_0,...,x_{2011}$ , we can make $x_n-x_0$ whatever we desire. WLOG, let $x_0\geq...\geq x_{2011}$ and let $a_n=x_n-x_0$ . Notice that, also, $m^{a_{2011}}$ doesn't matter if we are able to make $m^{a_1} +m^{a_2} + .... + m^{a_{2010}}$ equal to $1-\left(\frac{1}{m}\right)^x$ for any power of $x$ . Consider $m=2$ . We can achieve a sum of $1-\left(\frac{1}{2}\right)^x$ by doing $\frac{1}{2}+\frac{1}{4}+...$ (the "simplest" sequence). If we don't have $\frac{1}{2}$ , to compensate, we need $2\cdot \frac{1}{4}$ 's. Now, let's try to generalize. The "simplest" sequence is having $\frac{1}{m}$ $m-1$ times, $\frac{1}{m^2}$ $m-1$ times, $\ldots$ . To make other sequences, we can split $m-1$ $\frac{1}{m^i}$ s into $m(m-1)$ $\text{ }\frac{1}{m^{i+1}}$ s since $(m-1)\cdot\frac{1}{m^{i}} = m(m-1)\cdot\frac{1}{m^{i+1}}$ . Since we want $2010$ terms, we have $\sum$ $(m-1)\cdot m^x=2010$ . However, since we can set $x$ to be anything we want (including 0), all we care about is that $(m-1)\text{ }|\text{ } 2010$ which happens $\boxed{016}$ times.

Solution 2

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, if $P(m) = 0$ , then $m-1 | 2010$ . Now, we need to show that $m^{x_{0}}=\sum_{k = 1}^{2011}m^{x_{k}}\forall m-1|2010$ 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{016}$

Solution 3

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}$ .

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.$ 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}.$ 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{016}$ .

Solution 4 (for noobs like me)

The problem is basically asking how many integers $m$ have a power that can be expressed as the sum of 2011 other powers of $m$ (not necessarily distinct). Notice that $2+2+4+8+16=32$ , $3+3+3+9+9+27+27+81+81=243$ , and $4+4+4+4+16+16+16+64+64+64+256+256+256=1024$ . Thus, we can safely assume that the equation $2011 = (m-1)x + m$ must have an integer solution $x$ . To find the number of $m$ -values that allow the aforementioned equation to have an integer solution, we can subtract 1 from the constant $m$ to make the equation equal a friendlier number, $2010$ , instead of the ugly prime number $2011$ : $2010 = (m-1)x+(m-1)$ . Factor the equation and we get $2010 = (m-1)(x+1)$ . The number of values of $m-1$ that allow $x+1$ to be an integer is quite obviously the number of factors of $2010$ . Factoring $2010$ , we obtain $2010 = 2 \times 3 \times 5 \times 67$ , so the number of positive integers $m$ that satisfy the required condition is $2^4 = \boxed{016}$ .

-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 $m$ 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 $m$ -chopping is taking an existing block of say $m^{k}$ and turning it into $m$ blocks of $m^{k-1}$ . This process increases the total number of blocks by $m-1$ per chop.The problem wants us to find the number of positive integers $m$ where some number of chops will turn $1$ block into $2011$ such blocks, thus increasing the total amount by $2010= 2 \cdot 3 \cdot 5 \cdot 67$ . Thus $m-1 | 2010$ , and a cursory check on extreme cases will confirm that there are indeed $\boxed{016}$ possible $m$ s.

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^{n+1}$ or $m \cdot (m^n)$ , we have to add $m^n$ , $m-1$ times. Then when we are at $m^{n+1}$ , to get to $m^{n+2}$ , it is similar. So we have to have $m^{\text{some number}} = m^n + (m-1){m^n} + (m-1)(m^{n+1})\dots$ . This expression has $1 + (m-1) + (m-1) + \dots = 1 + k(m-1)$ terms, and the number of terms must be equal to $2011$ (as stated in the problem). Then $1+k(m-1) = 2011$ , and we get the equation $k(m-1) = 2010 = 2\cdot3\cdot5\cdot67$ . $2010$ has $16$ factors, and setting $m-1$ equal to each of these factors makes $\boxed{016}$ values of $m$ .

Solution 7 (xooks-rbo)

Take $\pmod {m-1}$ of both sides $m^{x_0} \equiv 1 \pmod {m-1}$ $\sum_{k = 1}^{2011} m^{x_k} \equiv 2011 \pmod {m-1}$ Setting both of these to be congruent to eachother, we get: $1 \equiv 2011 \pmod {m-1}$ Subtract $1$ from both sides to get: $0 \equiv 2010 \pmod {m-1}$ $m-1$ must be a factor of $2010$ .

$2010$ has $16$ factors, so there are $\boxed{16}$ values of $m$ .

Solution 8 (Polynomial Construction)

Let $f(a)$ be a polynomial in terms of $a$ , listed below, which has roots at the values $m$ that satisfy the problem condition: $f(a) = a^{x_0} - \sum_{k=1}^{2011} a^{x_k}$ It is evident to see that the polynomial has integer coefficients, which will be used later in the solution.

$f(1) = 1 - 2011 = -2010$ . We use the fact that polynomials $P(x)$ with integer coefficients satisfy the condition that $(a-b)|f(a)-f(b)$ for some integers $a$ and $b$ to conclude that $(m-1)|f(m)-f(1)$ Since $m$ is a solution of the polynomial, we have that $f(m) = 0$ . Therefore, we have that $(m-1)|2010$ Therefore, we arrive at the condition that $m-1$ must be a factor of $2010$ .

Since $2010=2\cdot 3\cdot 5\cdot 67$ , $2010$ has $16$ factors, so there are $\boxed{016}$ possible values of $m$ .

-Vivdax

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

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