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"

(Created page with '== Problem 7 == Find the number of positive integers <math>m</math> for which there exist nonnegative integers <math>x_0</math>, <math>x_1</math> , <math>\dots</math> , <math>x_{…')
 
(→‎Solution)
Line 6: Line 6:
 
NOTE: This solution is incomplete. Please help make it better.
 
NOTE: This solution is incomplete. Please help make it better.
  
−
This formula only works if <math>m</math> is exactly 1 more than a factor of 2010. (Someone else should insert a convincing proof here; I forgot exactly what I did. However, it involved starting with each <math>x_k</math> equal to an unspecified large number <math>q</math>, and then decreasing the powers of a certain number of the terms [equal to <math>m</math> to certain powers] by 1 repeatedly in certain ways until the expression becomes <math>m^p</math> • <math>m^q</math> for some integer p.)
+
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.
  
−
Since 2010 factors as <math>2^1 3^1 5^1 67^1</math>, there are <math>2^4=\boxed{016}</math> such factors.
+
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>.
  
 
== See also ==
 
== See also ==

Revision as of 15:19, 22 March 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.

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

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=37732"