Skip to main content

2010 AMC 10A Problem 25

Problem 25 of 25HarderAlgebraNumber TheoryProblem-Solving Techniques

Jim starts with a positive integer nn and creates a sequence of numbers. Each successive number is obtained by subtracting the largest possible integer square less than or equal to the current number until zero is reached. For example, if Jim starts with n=55,n = 55, then his sequence contains 55 numbers: 5555−72=66−22=22−12=11−12=0\begin{array}{ccccc} {}&{}&{}&{}&55\\ 55&-&7^2&=&6\\ 6&-&2^2&=&2\\ 2&-&1^2&=&1\\ 1&-&1^2&=&0\\ \end{array} Let NN be the smallest number for which Jim’s sequence has 88 numbers. What is the units digit of N?N?

Answer choices

Show solution

Solution

We can work backwards starting with 0.0. From this, we can add on 121^2 to get 1.1. We can again add on 121^2 to get 2.2. Again, adding on 121^2 gives us 3.3. If we add on 121^2 now, we get 4,4, but then 121^2 is not the greatest square less than or equal to 4.4. Then adding on 222^2 gives us 7.7. Continuing until there are eight terms in the forward sequence gives 7223.7223. 72237223−842=167167−122=2323−42=77−22=33−12=22−12=11−12=0\begin{array}{ccccc} {}&{}&{}&{}&7223\\ 7223&-&84^2&=&167\\ 167&-&12^2&=&23\\ 23&-&4^2&=&7\\ 7&-&2^2&=&3\\ 3&-&1^2&=&2\\2&-&1^2&=&1\\1&-&1^2&=&0\end{array} Thus, B is the correct answer.
AoPS wiki

Tagged: perfect square · recursion · work backwards

More practice