2012 AIME I Problems/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 .
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
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 .
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 .
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
|2012 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|