2012 AIME I Problems/Problem 10
Contents
Problem 10
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
and
are in different residue classes mod
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
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.