AMC 10 · 2010 · #25
Grade 7 number-theoryJim 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:
55621−−−−72221212====556210
Let N be the smallest number for which Jim’s sequence has 8 numbers. What is the units digit of N?
Pick an answer.
AMC 10 2010 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Jim starts with a positive integer and repeatedly subtracts the largest perfect square that is not larger than the current number, stopping when he reaches $0$. Counting the start, every in-between value, and the final $0$, the list of numbers has some length. Find the smallest starting value $N$ whose list is exactly $8$ numbers long, then report the units digit of that $N$.
Givens: Each step subtracts the largest perfect square $\le$ the current number.; The process stops when the value hits $0$.; For $n=55$ the list is $55,6,2,1,0$ — that is $5$ numbers.; We want the list to contain exactly $8$ numbers.; The answer choices give the units digit: (A) $1$, (B) $3$, (C) $5$, (D) $7$, (E) $9$.
Unknowns: The units digit of $N$, the smallest starting integer whose list has exactly $8$ numbers.
Understand
Restated: Jim starts with a positive integer and repeatedly subtracts the largest perfect square that is not larger than the current number, stopping when he reaches $0$. Counting the start, every in-between value, and the final $0$, the list of numbers has some length. Find the smallest starting value $N$ whose list is exactly $8$ numbers long, then report the units digit of that $N$.
Givens: Each step subtracts the largest perfect square $\le$ the current number.; The process stops when the value hits $0$.; For $n=55$ the list is $55,6,2,1,0$ — that is $5$ numbers.; We want the list to contain exactly $8$ numbers.; The answer choices give the units digit: (A) $1$, (B) $3$, (C) $5$, (D) $7$, (E) $9$.
Plan
Primary tool: #11 Work Backwards
Secondary: #4 Introduce a Variable, #14 Extreme Principle, #3 Eliminate Possibilities
Going forward is hopeless: we would have to test starting numbers one by one until one happens to take $7$ subtractions. The end of every list is the same — it is always $0$ — so Tool #11 (Work Backwards) fits perfectly. We start at $0$ and grow the list one term at a time, and at each stage we ask for the smallest number that could sit above the current one. To answer that we need Tool #4 (Introduce a Variable): call the square that gets subtracted $s^2$ and turn the phrase 'largest square not exceeding the value' into an inequality on $s$. Tool #14 (Extreme Principle) is what lets us trust the greedy choice — because the smallest predecessor grows when its target grows, taking the smallest option at every step really does give the smallest $N$ overall. Finally Tool #3 (Eliminate Possibilities) closes it: only one answer choice matches the units digit we compute.
Execute — Answer: B
6.EE.B.5 Step 1 Count steps, not numbers
- A list of $8$ numbers has $7$ arrows between them, so we need exactly $7$ subtractions.
- Since every list ends at $0$, put $0$ at the bottom and build upward, one row at a time, until $7$ rows sit above it.
- To get the smallest $N$, make each new row as small as possible.
💡 The finish line $0$ never changes, so it is far easier to grow the chain up from $0$ than to hunt for a starting number.
7.EE.B.4 Step 2 Rule for the smallest predecessor
- Suppose a row shows the value $c$.
- The row just above it must be $c+s^2$, where $s^2$ is the square Jim subtracts there.
- For $s^2$ to really be the largest square $\le c+s^2$, the value must stay below the next square $(s+1)^2$.
- Solving that inequality forces $s$ to be at least half of $c$.
- To keep the predecessor $c+s^2$ small, pick the smallest allowed $s$.
💡 If the subtracted square were too small, the leftover would spill past the next square and a bigger square would get used instead.
6.EE.A.1 Step 3 Build the chain upward
- Apply the rule seven times, each time choosing the smallest legal $s$ and adding $s^2$.
- Starting from $0$: add $1^2$ three times, then the required $s$ grows as the values climb.
- The squares used are $1,1,1,4,16,144,7056$.
💡 Each jump is forced to be the tiniest step that keeps the same subtracted square, so the ladder rises as slowly as it possibly can.
6.EE.B.5 Step 4 Why 7223 is truly the smallest
- The predecessor $c+s^2$ with $s\ge \tfrac{c}{2}$ gets larger whenever its target $c$ gets larger.
- So a smaller value on any row can never force a larger value above it.
- Choosing the smallest option at every single row therefore gives the smallest possible top number, $N=7223$.
- Its downward list $7223,167,23,7,3,2,1,0$ is indeed $8$ numbers.
💡 Because bigger targets need bigger predecessors, greedily picking the smallest each step can never be beaten.
6.EE.B.5 Step 5 Read the units digit
- The question only wants the units digit of $N$.
- The units digit of $7223$ is $3$, which matches exactly one answer choice.
💡 Only choice (B) ends in $3$, so every other option is ruled out at a glance.
6.EE.B.5 A list of $8$ numbers has $7$ arrows between them, so we need exactly $7$ subtra 7.EE.B.4 Suppose a row shows the value $c$. The row just above it must be $c+s^2$, where 6.EE.A.1 Apply the rule seven times, each time choosing the smallest legal $s$ and adding 6.EE.B.5 The predecessor $c+s^2$ with $s\ge \tfrac{c}{2}$ gets larger whenever its target 6.EE.B.5 The question only wants the units digit of $N$. The units digit of $7223$ is $3$ Review
Reasonableness: Run Jim's actual process forward on $7223$: the largest square $\le 7223$ is $84^2=7056$, leaving $167$; then $12^2=144$ leaves $23$; then $4^2=16$ leaves $7$; then $2^2=4$ leaves $3$; then $1,1,1$ subtract down through $2,1,0$. The list is $7223,167,23,7,3,2,1,0$ — exactly $8$ numbers, confirming the count. Any smaller start must, by the increasing-predecessor argument, produce a shorter list, so $7223$ is the minimum and its units digit $3$ gives (B).
Alternative: Instead of the inequality rule, one can tabulate the smallest number needing each list length by brute force: lengths $1,2,3,\dots$ first appear at $1,2,3,7,23,167,7223$. Watching that sequence, each new record is the previous one plus the square of the smallest integer at least half of it, which reproduces $7223$ without deriving the inequality abstractly.
CCSS standards used (min grade 7)
6.EE.A.1Write and evaluate numerical expressions involving whole-number exponents (Computing the subtracted squares such as $2^2=4$, $12^2=144$, and $84^2=7056$ while building the chain up to $7223$.)7.EE.B.4Use variables to represent quantities and construct simple equations and inequalities (Turning 'largest square not exceeding the value' into the inequality $c+s^2<(s+1)^2$ and solving it to get $s\ge \tfrac{c}{2}$.)6.EE.B.5Understand solving an equation or inequality as a process of finding values (Choosing the smallest $s$ that satisfies the constraint at each row, and arguing that greedy choices give the smallest overall $N$.)
⭐ Build the chain up from $0$ and always add the smallest square that keeps the same subtraction — the top of the shortest-growing ladder is the smallest starting number.
⭐ Build the chain up from $0$ and always add the smallest square that keeps the same subtraction — the top of the shortest-growing ladder is the smallest starting number.
More like this
Same archetype — closest grade level first.