Difference between revisions of "2012 AIME I Problems/Problem 10"
m (→Solution 2) |
(→Solution 1) |
||
(7 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
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 1== | == 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 | + | 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 \not\equiv s-16 \pmod{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== | == 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 | + | 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>1000|2000x</math> and <math>1000|2000000</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>. | 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>. | ||
Line 15: | Line 15: | ||
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. | 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 = | + | 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 = 6\boxed{170}256</math>. |
== Solution 3== | == Solution 3== | ||
Line 37: | Line 37: | ||
Rearranging terms, we get <math>y_2^2 - 16 = 125a_1</math>, whence difference of squares gives <math>(y_2 + 4)(y_2 - 4) = 125a_1</math>. Note that this equation tells us that one of <math>y_2 + 4</math> and <math>y_2 - 4</math> contains a nonnegative multiple of <math>125</math>. Hence, listing out the smallest possible values of <math>y_2</math>, we have <math>y_2 = 4, 121, 129, \cdots, 621</math>. The tenth term is <math>621</math>, whence <math>y = 4y_2 = 2484</math>. The desired result can then be calculated to be <math>\boxed{170}</math>. - Spacesam | Rearranging terms, we get <math>y_2^2 - 16 = 125a_1</math>, whence difference of squares gives <math>(y_2 + 4)(y_2 - 4) = 125a_1</math>. Note that this equation tells us that one of <math>y_2 + 4</math> and <math>y_2 - 4</math> contains a nonnegative multiple of <math>125</math>. Hence, listing out the smallest possible values of <math>y_2</math>, we have <math>y_2 = 4, 121, 129, \cdots, 621</math>. The tenth term is <math>621</math>, whence <math>y = 4y_2 = 2484</math>. The desired result can then be calculated to be <math>\boxed{170}</math>. - Spacesam | ||
+ | |||
+ | == Solution 5 (Similar to Solution 4) == | ||
+ | From the conditions, we can let every element in <math>\mathcal{S}</math> be written as <math>y^2=1000x+256</math>, where <math>x</math> and <math>y</math> are integers. Since there are no restrictions on <math>y</math>, we let <math>y_1</math> be equal to <math>y+16</math> (<math>y-16</math> works as well). Then the <math>256</math> cancels out and we're left with <cmath>y_1^2+32y_1=1000x</cmath> which can be factored as <cmath>y_1(y_1+32)=1000x</cmath> Since the RHS is even, <math>y_1</math> must be even, so we let <math>y_1=2y_2</math>, to get <cmath>y_2(y_2+16)=250x</cmath> Again, because the RHS is even, the LHS must be even too, so substituting <math>y_3=\frac{1}{2}y_2</math> we have <cmath>y_3(y_3+8)=125\cdot\frac{1}{2}x</cmath> Since the LHS is an integer, the RHS must thus be an integer, so substituting <math>x=2x_1</math> we get <cmath>y_3(y_3+8)=125x_1</cmath> Then we can do casework on the values of <math>y_3</math>, as only one of <math>y_3</math> and <math>y_3+8</math> can be multiples of <math>125</math> | ||
+ | |||
+ | '''Case 1''': <math>125|y_3</math> | ||
+ | |||
+ | Since we're trying to find the values of <math>x_1</math>, we can let <math>y_4=\frac{1}{125}y_3</math>, to get <cmath>x_1=y_4(125y_4+8)</cmath> or <cmath>x=2y_4(125y_4+8)</cmath> | ||
+ | |||
+ | '''Case 2''': <math>125|y_3+8</math> | ||
+ | |||
+ | Similar to Case 1, only the equation is <cmath>x=2y_4(125y_4-8)</cmath> | ||
+ | |||
+ | In whole, the values of <math>x</math> (i.e. the elements in <math>\mathcal{T}</math>) are of the form <cmath>x=2k(125k\pm8)</cmath> where <math>k</math> is any integer. It can easily be seen that if <math>k<0</math>, then <math>x</math> is negative, thus <math>k\geq0</math>. Also, note that when <math>k=0</math>, there is only one value, because one of the factors is <math>0</math> (<math>k</math>). Thus the <math>10^{th}</math> smallest number in the set <math>\mathcal{T}</math> is when the <math>\pm</math> sign takes the minus side and <math>k=5</math>, giving <math>6170</math>, so the answer is <math>\boxed{170}</math> | ||
+ | |||
+ | == Video Solution by Richard Rusczyk == | ||
+ | |||
+ | https://artofproblemsolving.com/videos/amc/2012aimei/349 | ||
+ | |||
+ | ~ dolphin7 | ||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | https://www.youtube.com/watch?v=caCELHibbIE&list=PLOaAlyCEsUTbA2v1gRyEAB_gxk7NiWG3v&index=6&t=0s | ||
+ | |||
+ | ~Shreyas S | ||
== 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}} |
Latest revision as of 02:03, 25 November 2023
Contents
Problem
Let be the set of all perfect squares whose rightmost three digits in base
are
. Let
be the set of all numbers of the form
, where
is in
. In other words,
is the set of numbers that result when the last three digits of each number in
are truncated. Find the remainder when the tenth smallest element of
is divided by
.
Solution 1
It is apparent that for a perfect square to satisfy the constraints, we must have
or
Now in order for
to be a multiple of
at least one of
and
must be a multiple of
and since
one term must have all the factors of
and thus must be a multiple of
Furthermore, each of
and
must have at least two factors of
since otherwise
could not possibly be divisible by
So therefore the conditions are satisfied if either
or
is divisible by
or equivalently if
Counting up from
to
we see that the tenth value of
is
and thus the corresponding element in
is
Solution 2
Notice that is ,
ends in
. In general, if
ends in
,
ends in 256 because
and
. It is clear that we want all numbers whose squares end in
that are less than
.
Firstly, we know the number has to end in a or a
. Let's look at the ones ending in
.
Assume that the second digit of the three digit number is . We find that the last
digits of
is in the form
. However, the last two digits need to be a
. Thus, similarly trying all numbers from
to
, we see that only 1 for the middle digit works. Carrying out the multiplication, we see that the last
digits of
is in the form
. We want
to be equal to
. Thus, we see that a is
or
. Thus, the numbers that work in this case are
and
.
Next, let's look at the ones ending in . Carrying out a similar technique as above, we see that the last
digits of
is in the form
. We want
to be equal to
. We see that only
and
work. Thus, we see that only
and
work.
We order these numbers to get ,
,
,
... We want the
number in order which is
.
Solution 3
The condition implies . Rearranging and factoring,
This can be expressed with the system of congruences
Observe that
or
. Similarly, it can be seen that
or
. By CRT, there are four solutions to this modulo
(one for each case e.g.
and
or
and
. These solutions are (working modulo
)
The tenth solution is
which gives an answer of
.
Solution 4
An element in S can be represented by , where
is the element in S. Since the right hand side must be even, we let
and substitute to get
. However, the right hand side is still even, so we make the substitution
to get
. Because both sides must be an integer, we know that
for some integer
. Our equation then becomes
, and we can simplify no further.
Rearranging terms, we get , whence difference of squares gives
. Note that this equation tells us that one of
and
contains a nonnegative multiple of
. Hence, listing out the smallest possible values of
, we have
. The tenth term is
, whence
. The desired result can then be calculated to be
. - Spacesam
Solution 5 (Similar to Solution 4)
From the conditions, we can let every element in be written as
, where
and
are integers. Since there are no restrictions on
, we let
be equal to
(
works as well). Then the
cancels out and we're left with
which can be factored as
Since the RHS is even,
must be even, so we let
, to get
Again, because the RHS is even, the LHS must be even too, so substituting
we have
Since the LHS is an integer, the RHS must thus be an integer, so substituting
we get
Then we can do casework on the values of
, as only one of
and
can be multiples of
Case 1:
Since we're trying to find the values of , we can let
, to get
or
Case 2:
Similar to Case 1, only the equation is
In whole, the values of (i.e. the elements in
) are of the form
where
is any integer. It can easily be seen that if
, then
is negative, thus
. Also, note that when
, there is only one value, because one of the factors is
(
). Thus the
smallest number in the set
is when the
sign takes the minus side and
, giving
, so the answer is
Video Solution by Richard Rusczyk
https://artofproblemsolving.com/videos/amc/2012aimei/349
~ dolphin7
Video Solution
https://www.youtube.com/watch?v=caCELHibbIE&list=PLOaAlyCEsUTbA2v1gRyEAB_gxk7NiWG3v&index=6&t=0s
~Shreyas S
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.