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"

(→‎See also)
(Proof of sufficiency)
Line 10: Line 10:
 
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.
 
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.
  
−
I will consider the example of <math>m=3</math> to give a sense of why <math>m</math> will work so long as <math>m-1</math> divides 2010.  We can write <math>2187 = 3^7 = \sum_{i=1}^{3^7} 3^0</math>.  Exchanging three <math>3^0</math> terms for a <math>3^1</math> term leaves the value on the right the same and decreases the number of terms by 2.  Thus, we can write <math>3^7=2187</math> using <math>2187</math> terms, or <math>2185, 2183, \dots</math>, where the pattern is that the number of possible terms is <math>\equiv 1 \pmod{2}</math>.  Since <math>2 | 2010 = 2011-1</math>, <math>m=3</math> is a value of <math>m</math> for which we can obtain the desired sum.  If we run out of <math>3^0</math> terms, we can start exchanging three <math>3^1</math> terms for a <math>3^2</math> term.  In general, this exchange will take <math>m</math> terms of <math>m^k</math> and replace them with one <math>m^{k+1}</math> term, thus reducing the number of terms by <math>(m-1)</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.
  
 
== See also ==
 
== See also ==

Revision as of 12:42, 18 May 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

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 (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=38623"