Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 AIME I Problems/Problem 7"

(Proof of sufficiency)
(→‎Solution)
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
−
NOTE: This solution is incomplete. Please help make it better.
+
One notices that <math>m-1 \mid 2010</math>  if and only if there exist non-negative integers <math>x_0,x_1,\ldots,x_{2011}</math> such that <math>m^{x_0} = \sum_{k=1}^{2011}m^{x^k}</math>.
  
−
This formula only works if <math>m</math> is exactly 1 more than a factor of 2010. Since 2010 factors as <math>2^1 3^1 5^1 67^1</math>, there are <math>2^4=\boxed{016}</math> such factors.
+
To prove the forward case, we proceed by directly finding <math>x_0,x_1,\ldots,x_{2011}</math>. Suppose <math>m</math> is an integer such that <math>m^{x_0} = \sum_{k=1}^{2011}m^{x^k}</math>. We will count how many <math>x_k = 0</math>, how many <math>x_k = 1</math>, etc. Suppose the number of <math>x_k = 0</math> is non-zero. Then, there must be at least <math>m</math> such <math>x_k</math> since <math>m</math> divides all the remaining terms, so <math>m</math> must also divide the sum of all the <math>m^0</math> terms. Thus, if we let <math>x_k = 0</math> for <math>k = 1,2,\ldots,m</math>, we have,
 +
<cmath>m^{x_0} = m + \sum_{k=m+1}^{2011}m^{x_k}.</cmath>
 +
Well clearly, <math>m^{x_0}</math> is greater than <math>m</math>, so <math>m^2 \mid m^{x_0}</math>. <math>m^2</math> will also divide every term, <math>m^{x_k}</math>, where <math>x_k \geq 2</math>. So, all the terms, <math>m^{x_k}</math>, where <math>x_k < 2</math> must sum to a multiple of <math>m^2</math>. If there are exactly <math>m</math> terms where <math>x_k = 0</math>, then we must have at least <math>m-1</math> terms where <math>x_k = 1</math>. Suppose there are exactly <math>m-1</math> such terms and <math>x_k = 1</math> for <math>k = m+1,m+2,2m-1</math>. Now, we have,
 +
<cmath>m^{x_0} = m^2 + \sum_{k=2m}^{2011}m^{x_k}.</cmath>
 +
One can repeat this process for successive powers of <math>m</math> until the number of terms reaches 2011. Since there are <math>m + j(m-1)</math> terms after the <math>j</math>th power, we will only hit exactly 2011 terms if <math>m-1</math> is a factor of 2010. To see this,
 +
<cmath>m+j(m-1) = 2011 \Rightarrow m-1+j(m-1) &= 2010 \Rightarrow (m-1)(j+1) = 2010.</cmath>
 +
Thus, when <math>j = 2010/(m-1) - 1</math> (which is an integer since <math>m-1 \mid 2010</math> by assumption, there are exactly 2011 terms. To see that these terms sum to a power of <math>m</math>, we realize that the sum is a geometric series:
 +
<cmath>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}.</cmath>
 +
Thus, we have found a solution for the case <math>m-1 \mid 2010</math>.
  
−
First I show that <math>m-1</math> must divide <math>2010</math>.  Consider the desired equation <math>\pmod{m-1}</math>. The left side is <math>\equiv 1</math>, whereas the right side is <math>\equiv 2011</math>. Thus, we have <math>1 \equiv 2011 \pmod{m-1}</math>, so <math>m-1</math> must divide 2010.
+
Now, for the reverse case, we use the formula <cmath>x^k-1 = (x-1)(x^{k-1}+x^{k-2}+\cdots+1).</cmath> Suppose <math>m^{x_0} = \sum_{k=1}^{2011}m^{x^k}</math> has a solution. Subtract 2011 from both sides to get <cmath>m^{x_0}-1-2010 = \sum_{k=1}^{2011}(m^{x^k}-1).</cmath> Now apply the formula to get <cmath>(m-1)a_0-2010 = \sum_{k=1}^{2011}[(m-1)a_k],</cmath> where <math>a_k</math> are some integers. Rearranging this equation, we find <cmath>(m-1)A = 2010,</cmath> where <math>A = a_0 - \sum_{k=1}^{2011}a_k</math>. Thus, if <math>m</math> is a solution, then <math>m-1 \mid 2010</math>.  
  
−
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.
+
So, there is one positive integer solution corresponding to each factor of 2010. Since <math>2010 = 2\cdot 3\cdot 5\cdot 67</math>, the number of solutions is <math>2^4 = \boxed{16}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 06:19, 3 June 2011

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

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.\] (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}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_I_Problems/Problem_7&oldid=39044"