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 "2012 AIME I Problems/Problem 10"
(→‎Solution)
Line 3: Line 3:
 
Let <math>\mathcal{S}</math> be the set of all perfect squares whose rightmost three digits in base <math>10</math> are <math>256</math>. Let <math>\mathcal{T}</math> be the set of all numbers of the form <math>\frac{x-256}{1000}</math>, where <math>x</math> is in <math>\mathcal{S}</math>. In other words, <math>\mathcal{T}</math> is the set of numbers that result when the last three digits of each number in <math>\mathcal{S}</math> are truncated. Find the remainder when the tenth smallest element of <math>\mathcal{T}</math> is divided by <math>1000</math>.
 
Let <math>\mathcal{S}</math> be the set of all perfect squares whose rightmost three digits in base <math>10</math> are <math>256</math>. Let <math>\mathcal{T}</math> be the set of all numbers of the form <math>\frac{x-256}{1000}</math>, where <math>x</math> is in <math>\mathcal{S}</math>. In other words, <math>\mathcal{T}</math> is the set of numbers that result when the last three digits of each number in <math>\mathcal{S}</math> are truncated. Find the remainder when the tenth smallest element of <math>\mathcal{T}</math> is divided by <math>1000</math>.
  
−
== Solution ==
+
== Solution 1==
 
It is apparent that for a perfect square <math>s^2</math> to satisfy the constraints, we must have <math>s^2 - 256 = 1000n</math> or <math>(s+16)(s-16) = 1000n.</math> Now in order for <math>(s+16)(s-16)</math> to be a multiple of <math>1000,</math> at least one of <math>s+16</math> and <math>s-16</math> must be a multiple of <math>5,</math> and since <math>s+16</math> and <math>s-16</math> are in different residue classes mod <math>5,</math> one term must have all the factors of <math>5</math> and thus must be a multiple of <math>125.</math> Furthermore, each of <math>s+16</math> and <math>s-16</math> must have at least two factors of <math>2,</math> since otherwise <math>(s+16)(s-16)</math> could not possibly be divisible by <math>8.</math> So therefore the conditions are satisfied if either <math>s+16</math> or <math>s-16</math> is divisible by <math>500,</math> or equivalently if <math>s = 500n \pm 16.</math> Counting up from <math>n=0</math> to <math>n=5,</math> we see that the tenth value of <math>s</math> is <math>500 \cdot 5 - 16 = 2484</math> and thus the corresponding element in <math>\mathcal{T}</math> is <math>\frac{2484^2 - 256}{1000} = 6170 \rightarrow \boxed{170.}</math>
 
It is apparent that for a perfect square <math>s^2</math> to satisfy the constraints, we must have <math>s^2 - 256 = 1000n</math> or <math>(s+16)(s-16) = 1000n.</math> Now in order for <math>(s+16)(s-16)</math> to be a multiple of <math>1000,</math> at least one of <math>s+16</math> and <math>s-16</math> must be a multiple of <math>5,</math> and since <math>s+16</math> and <math>s-16</math> are in different residue classes mod <math>5,</math> one term must have all the factors of <math>5</math> and thus must be a multiple of <math>125.</math> Furthermore, each of <math>s+16</math> and <math>s-16</math> must have at least two factors of <math>2,</math> since otherwise <math>(s+16)(s-16)</math> could not possibly be divisible by <math>8.</math> So therefore the conditions are satisfied if either <math>s+16</math> or <math>s-16</math> is divisible by <math>500,</math> or equivalently if <math>s = 500n \pm 16.</math> Counting up from <math>n=0</math> to <math>n=5,</math> we see that the tenth value of <math>s</math> is <math>500 \cdot 5 - 16 = 2484</math> and thus the corresponding element in <math>\mathcal{T}</math> is <math>\frac{2484^2 - 256}{1000} = 6170 \rightarrow \boxed{170.}</math>
 +
 +
== Solution 2==
 +
Notice that is <math>16^2=256</math>, <math>1016^2</math> ends in <math>256</math>. In general, if <math>x^2</math> ends in <math>256</math>, <math>(x+1000)^2=x^2+2000x+1000000</math> ends in 256 because <math>2000x >1000</math> and <math>2000000 > 1000</math>. It is clear that we want all numbers whose squares end in <math>256</math> that are less than <math>1000</math>.
 +
 +
Firstly, we know the number has to end in a <math>4</math> or a <math>6</math>. Let's look at the ones ending in <math>6</math>.
 +
 +
Assume that the second digit of the three digit number is <math>0</math>. We find that the last <math>3</math> digits of <math>\overline{a06}^2</math> is in the form <math>12a \cdot 100 + 3 \cdot 10 + 6</math>. However, the last two digits need to be a <math>56</math>. Thus, similarly trying all numbers from <math>0</math> to <math>10</math>, we see that only 1 for the middle digit works. Carrying out the multiplication, we see that the last <math>3</math> digits of <math>\overline{a06}^2</math> is in the form <math>(12a + 2) \cdot 100 + 5 \cdot 10 + 6</math>. We want <math>(12a + 2)\pmod{10}</math> to be equal to <math>2</math>. Thus, we see that a is <math>0</math> or <math>5</math>. Thus, the numbers that work in this case are <math>016</math> and <math>516</math>.
 +
 +
Next, let's look at the ones ending in <math>4</math>. Carrying out a similar technique as above, we see that the last <math>3</math> digits of <math>\overline{a84}^2</math> is in the form <math>((8a+10) \cdot 100+ 5 \cdot 10 + 6</math>. We want <math>(8a + 10)\pmod{10}</math> to be equal to <math>2</math>. We see that only <math>4</math> and <math>9</math> work. Thus, we see that only <math>484</math> and <math>984</math> work.
 +
 +
We order these numbers to get  <math>16</math>, <math>484</math>, <math>516</math>  <math>984</math>. We want the <math>10th</math> number in order which is <math>2484^2 = 6170256</math>.  <math>\boxed{170}</math>
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2012|n=I|num-b=9|num-a=11}}
 
{{AIME box|year=2012|n=I|num-b=9|num-a=11}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 13:57, 6 July 2015

Problem 10

Let $\mathcal{S}$ be the set of all perfect squares whose rightmost three digits in base $10$ are $256$. Let $\mathcal{T}$ be the set of all numbers of the form $\frac{x-256}{1000}$, where $x$ is in $\mathcal{S}$. In other words, $\mathcal{T}$ is the set of numbers that result when the last three digits of each number in $\mathcal{S}$ are truncated. Find the remainder when the tenth smallest element of $\mathcal{T}$ is divided by $1000$.

Solution 1

It is apparent that for a perfect square $s^2$ to satisfy the constraints, we must have $s^2 - 256 = 1000n$ or $(s+16)(s-16) = 1000n.$ Now in order for $(s+16)(s-16)$ to be a multiple of $1000,$ at least one of $s+16$ and $s-16$ must be a multiple of $5,$ and since $s+16$ and $s-16$ are in different residue classes mod $5,$ one term must have all the factors of $5$ and thus must be a multiple of $125.$ Furthermore, each of $s+16$ and $s-16$ must have at least two factors of $2,$ since otherwise $(s+16)(s-16)$ could not possibly be divisible by $8.$ So therefore the conditions are satisfied if either $s+16$ or $s-16$ is divisible by $500,$ or equivalently if $s = 500n \pm 16.$ Counting up from $n=0$ to $n=5,$ we see that the tenth value of $s$ is $500 \cdot 5 - 16 = 2484$ and thus the corresponding element in $\mathcal{T}$ is $\frac{2484^2 - 256}{1000} = 6170 \rightarrow \boxed{170.}$

Solution 2

Notice that is $16^2=256$, $1016^2$ ends in $256$. In general, if $x^2$ ends in $256$, $(x+1000)^2=x^2+2000x+1000000$ ends in 256 because $2000x >1000$ and $2000000 > 1000$. It is clear that we want all numbers whose squares end in $256$ that are less than $1000$.

Firstly, we know the number has to end in a $4$ or a $6$. Let's look at the ones ending in $6$.

Assume that the second digit of the three digit number is $0$. We find that the last $3$ digits of $\overline{a06}^2$ is in the form $12a \cdot 100 + 3 \cdot 10 + 6$. However, the last two digits need to be a $56$. Thus, similarly trying all numbers from $0$ to $10$, we see that only 1 for the middle digit works. Carrying out the multiplication, we see that the last $3$ digits of $\overline{a06}^2$ is in the form $(12a + 2) \cdot 100 + 5 \cdot 10 + 6$. We want $(12a + 2)\pmod{10}$ to be equal to $2$. Thus, we see that a is $0$ or $5$. Thus, the numbers that work in this case are $016$ and $516$.

Next, let's look at the ones ending in $4$. Carrying out a similar technique as above, we see that the last $3$ digits of $\overline{a84}^2$ is in the form $((8a+10) \cdot 100+ 5 \cdot 10 + 6$. We want $(8a + 10)\pmod{10}$ to be equal to $2$. We see that only $4$ and $9$ work. Thus, we see that only $484$ and $984$ work.

We order these numbers to get $16$, $484$, $516$ $984$. We want the $10th$ number in order which is $2484^2 = 6170256$. $\boxed{170}$

See also

2012 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_AIME_I_Problems/Problem_10&oldid=71007"