2010 AMC 10A Problem 25

P21-25~10 minPrint

Number Properties Sequences & Series Consider the largest/smallest element or boundary case Start from the end state / desired conclusion and reverse

Jim starts with a positive integer $n$ 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$ , then his sequence contains $5$ numbers:

$\begin{array}{ccccc} {}&{}&{}&{}&55\\ 55&-&7^2&=&6\\ 6&-&2^2&=&2\\ 2&-&1^2&=&1\\ 1&-&1^2&=&0\\ \end{array}$

Let $N$ be the smallest number for which Jim’s sequence has $8$ numbers. What is the units digit of $N$ ?

Show solution without answering

Key insight

Work backwards. If m squared is the largest square below n, the leftover is at most 2m, so each smallest start is the previous one plus the smallest allowed square.

Solution

A sequence with $8$ numbers takes $7$ subtractions to reach $0$ . So we want the smallest number that needs $7$ steps. Build the answer up from small cases.

Step 1: small cases by hand. Write "steps" for the number of subtractions.

Start	Sequence	Steps
$1$	$1 \to 0$	$1$
$2$	$2 \to 1 \to 0$	$2$
$3$	$3 \to 2 \to 1 \to 0$	$3$
$7$	$7 \to 3 \to 2 \to 1 \to 0$	$4$

(Numbers $4$ , $5$ , $6$ go to $0$ , $1$ , $2$ in one step, so they need at most $3$ steps. So $7$ is the smallest needing $4$ .)

Step 2: how big can the leftover be? Suppose the largest square not above $n$ is $m^2$ , and the leftover is $r = n - m^2$ . The next square, $(m+1)^2 = m^2 + 2m + 1$ , is bigger than $n$ . So
$r \le 2m.$
For example, with $m = 2$ the leftover can be at most $4$ (the numbers $4$ to $8$ ).

Step 3: the rule for going one step deeper. To need one more step than some number $s$ , the first subtraction must leave a number that needs as many steps as $s$ . The smallest such start is: leftover exactly $s$ (the smallest leftover that works), plus the smallest square $m^2$ that is allowed, which needs $2m \ge s$ .

5 steps: leftover $7$ needs $2m \ge 7$ , so $m = 4$ . Start $= 16 + 7 = 23$ .
6 steps: leftover $23$ needs $2m \ge 23$ , so $m = 12$ . Start $= 144 + 23 = 167$ .
7 steps: leftover $167$ needs $2m \ge 167$ , so $m = 84$ . Start $= 84^2 + 167 = 7056 + 167 = 7223$ .

Step 4: why nothing smaller works. A start with $7$ steps must leave, after one subtraction, a number that needs $6$ steps, so that leftover is at least $167$ . Then $2m \ge 167$ forces $m \ge 84$ , and the start is at least $84^2 + 167 = 7223$ . The same reasoning checks each earlier row.

Step 5: check the sequence. $85^2 = 7225$ is more than $7223$ , so $84^2$ really is the largest square. The sequence is
$7223 \to 167 \to 23 \to 7 \to 3 \to 2 \to 1 \to 0,$
which has $8$ numbers.

So $N = 7223$ , and its units digit is $3$ .

The answer is $\boxed{\textbf{(B)}\ 3}$ .

Why this works

To find the smallest number that takes many steps, work backwards: the number after the first step must itself be the smallest one that takes one step fewer. The only limit is that the leftover can be at most twice $m$ , where $m^2$ is the square you subtract, which is why each answer is roughly the square of half the previous one.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Let $f(n)$ be the number of subtractions needed to reach $0$ ; the sequence then has $f(n) + 1$ numbers, so we want the smallest $n$ with $f(n) = 7$ . Let $s_k$ denote the smallest $n$ with $f(n) = k$ .

Write $n = m^2 + r$ where $m^2$ is the largest square not exceeding $n$ ; then $0 \le r \le 2m$ (otherwise $(m+1)^2 \le n$ ), and the first step sends $n$ to $r$ , so $f(n) = 1 + f(r)$ .

For $f(n) = k + 1$ we need $f(r) = k$ , hence $r \ge s_k$ , and then $2m \ge r \ge s_k$ forces $m \ge \lceil s_k/2 \rceil$ . So $n \ge \lceil s_k/2 \rceil^2 + s_k$ . This bound is attained: with $m = \lceil s_k/2 \rceil$ and $r = s_k \le 2m$ , the number $m^2 + s_k$ really has $m^2$ as its largest square, and it needs exactly $k+1$ steps. Therefore
$s_{k+1} = \left\lceil \tfrac{s_k}{2} \right\rceil^2 + s_k.$

Starting from $s_1 = 1$ :
$s_2 = 1 + 1 = 2,\quad s_3 = 1 + 2 = 3,\quad s_4 = 2^2 + 3 = 7,\quad s_5 = 4^2 + 7 = 23,$
$s_6 = 12^2 + 23 = 167,\quad s_7 = 84^2 + 167 = 7056 + 167 = 7223.$

(Check: $85^2 = 7225 > 7223$ , so $84^2$ is indeed the largest square, and $7223 \to 167 \to 23 \to 7 \to 3 \to 2 \to 1 \to 0$ is $7$ steps.)

So $N = 7223$ , whose units digit is $3$ .

The answer is $\boxed{\textbf{(B)}\ 3}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.4)
Introduction to Algebra, Chapter 20: Special Functions (§20.3)