2010 AMC 10A Problem 25

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.

(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}$.

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.

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}$.