2010 AMC 10A Problem 25

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

The process is a recursion $n \mapsto n - m^2$, and the minimal input for a given depth is built backwards: the remainder after the first step must itself be a minimal deep input, and the square removed must be just large enough that the remainder is legal. The inequality $r \le 2m$ is the whole content; it is what makes each level roughly the square of half the previous one.

• Forgetting the constraint r <= 2m (so that m^2 is really the largest square below n) and choosing a smaller m, or miscounting: 8 numbers in the sequence means 7 subtractions.
• Guessing that the minimal number at each level is the previous one plus the next square, rather than working out which $m$ is forced.