AMC 10 · 2002 · #22
Grade 8 number-theoryA set of tiles numbered 1 through 100 is modified repeatedly by the following operation: remove all tiles numbered with a perfect square, and renumber the remaining tiles consecutively starting with 1. How many times must the operation be performed to reduce the number of tiles in the set to one?
Pick an answer.
AMC 10 2002 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: You start with $100$ tiles numbered $1$ through $100$. One operation does two things: first throw away every tile whose number is a perfect square ($1,4,9,\dots$), then renumber the tiles that are left $1,2,3,\dots$ with no gaps. Repeat the whole operation over and over. Count how many operations it takes until only one tile remains.
Givens: The starting set is tiles numbered $1$ through $100$, so there are $100$ tiles; Each operation removes exactly the tiles whose current number is a perfect square; After removing, the survivors are renumbered $1,2,3,\dots$ so the set is again $1$ through (new count); Answer choices: (A) $10$, (B) $11$, (C) $18$, (D) $19$, (E) $20$
Unknowns: The number of operations needed to bring the set down to exactly one tile
Understand
Restated: You start with $100$ tiles numbered $1$ through $100$. One operation does two things: first throw away every tile whose number is a perfect square ($1,4,9,\dots$), then renumber the tiles that are left $1,2,3,\dots$ with no gaps. Repeat the whole operation over and over. Count how many operations it takes until only one tile remains.
Givens: The starting set is tiles numbered $1$ through $100$, so there are $100$ tiles; Each operation removes exactly the tiles whose current number is a perfect square; After removing, the survivors are renumbered $1,2,3,\dots$ so the set is again $1$ through (new count); Answer choices: (A) $10$, (B) $11$, (C) $18$, (D) $19$, (E) $20$
Plan
Primary tool: #5 Look for a Pattern
Secondary: #4 Introduce a Variable, #9 Solve an Easier Related Problem
Simulating all the way from $100$ tile-by-tile is slow, so tool #5 (Look for a Pattern) leads: run the operation a couple of times and watch the count drop from $100$. The key thing to notice is that only the number of tiles matters, because after each step the tiles are renumbered $1,2,3,\dots$ again. To see WHY the pattern holds, tool #4 (Introduce a Variable) lets us call the count $n$ and note that one operation removes exactly the perfect squares $\le n$. Tool #9 (Solve an Easier Related Problem) sharpens this: test what happens when the count is a perfect square $n=k^2$, and a clean rule appears — two operations always turn $k^2$ tiles into $(k-1)^2$ tiles. Then counting the operations is just counting how many times you step a perfect square down from $10^2$ to $1^2$.
Execute — Answer: C
6.EE.A.1 Step 1 Run the operation twice and watch the count
- Only the number of tiles matters, since after each step the survivors are renumbered $1,2,3,\dots$ again.
- Start with $100$ tiles.
- The perfect squares from $1$ to $100$ are $1,4,9,16,25,36,49,64,81,100$ — that is $10$ of them — so the first operation removes $10$ tiles and leaves $100-10=90$.
- Now there are $90$ tiles.
- The perfect squares from $1$ to $90$ are $1,4,\dots,81$ — that is $9$ of them (since $9^2=81\le 90$ but $10^2=100>90$) — so the second operation removes $9$ tiles and leaves $90-9=81$.
- Notice $81=9^2$ is itself a perfect square.
- So two operations took us from $100=10^2$ down to $81=9^2$.
💡 Because the tiles are renumbered each time, the only thing that changes is the head count.
8.EE.A.2 Step 2 Count removals with a square root
- Name the current count $n$.
- One operation removes every tile whose number is a perfect square, and the perfect squares up to $n$ are $1^2,2^2,\dots$ up to the largest square that is $\le n$.
- That largest one is $\lfloor\sqrt{n}\rfloor^2$, so the number of tiles removed is exactly $\lfloor\sqrt{n}\rfloor$ — the biggest whole number whose square does not exceed $n$.
- For example with $n=90$, $\sqrt{90}\approx 9.49$, so $\lfloor\sqrt{90}\rfloor=9$ tiles come off, matching what we saw.
- This gives one clean rule for every step: from $n$ tiles you go to $n-\lfloor\sqrt{n}\rfloor$ tiles.
💡 The count of perfect squares up to $n$ is just how far you can go before a square passes $n$, namely $\lfloor\sqrt{n}\rfloor$.
6.EE.A.3 Step 3 Two operations drop one perfect square
- Test the rule on a perfect square $n=k^2$.
- First operation: $\lfloor\sqrt{k^2}\rfloor=k$, so it removes $k$ tiles and leaves $k^2-k$.
- Now how many squares are $\le k^2-k$?
- Since $(k-1)^2=k^2-2k+1$ is $\le k^2-k$ (whenever $k\ge 1$) but $k^2$ is bigger than $k^2-k$, the largest square $\le k^2-k$ is $(k-1)^2$, so $\lfloor\sqrt{k^2-k}\rfloor=k-1$.
- Second operation removes $k-1$ tiles, leaving $k^2-k-(k-1)=k^2-2k+1=(k-1)^2$.
- So two operations always carry $k^2$ tiles down to $(k-1)^2$ tiles.
- This matches step 1: $10^2\to 9^2$.
💡 After pulling $k$ tiles off a square count, you land just above the next lower square, so one more pull settles exactly onto it.
4.OA.C.5 Step 4 Step the squares down and count
- Apply the two-operations rule repeatedly, watching the perfect-square base fall by $1$ each time: $10^2\to 9^2\to 8^2\to\cdots\to 2^2\to 1^2$.
- Reaching $1^2=1$ means one tile is left, which is the stopping point.
- Going from base $10$ down to base $1$ is $9$ steps down, and each step costs $2$ operations, giving $9\times 2=18$ operations.
- (Direct check on the last stretch: $4$ tiles remove $2$ to give $2$, then $2$ tiles remove $1$ to give $1$ — the $17$th and $18$th operations.) So it takes $18$ operations, which is choice (C).
💡 Each pair of operations knocks the square base down by one, so nine knocks take $10^2$ all the way to a single tile.
6.EE.A.1 Only the number of tiles matters, since after each step the survivors are renumb 8.EE.A.2 Name the current count $n$. One operation removes every tile whose number is a p 6.EE.A.3 Test the rule on a perfect square $n=k^2$. First operation: $\lfloor\sqrt{k^2}\r 4.OA.C.5 Apply the two-operations rule repeatedly, watching the perfect-square base fall Review
Reasonableness: Simulate the count straight through to be sure: $100\to 90\to 81\to 72\to 64\to 56\to 49\to 42\to 36\to 30\to 25\to 20\to 16\to 12\to 9\to 6\to 4\to 2\to 1$. Counting the arrows gives $18$ operations, and every perfect-square value ($81,64,49,36,25,16,9,4,1$) shows up exactly where the two-step rule predicts. The answer $18$ also sits sensibly among the choices: a naive guess might be $10$ (once per starting square) or $20$ (twice per square for ten squares), but the process ends at $1^2$ after only $9$ square-drops, so $18$, not $20$, is right.
Alternative: Instead of the square-root count, just track the number of remaining tiles and repeatedly subtract the number of perfect squares $\le$ that count, keeping a tally: $100,90,81,72,64,56,49,42,36,30,25,20,16,12,9,6,4,2,1$. There are $18$ subtractions before hitting $1$. This brute-force count needs no algebra and confirms the pattern answer of $18$.
CCSS standards used (min grade 8)
6.EE.A.1Write and evaluate numerical expressions involving whole-number exponents (Recognizing perfect squares $1,4,9,\dots,100$ and reading $100=10^2$, $81=9^2$ as squares to see the count drop.)8.EE.A.2Use square root and cube root symbols to represent solutions (Counting the perfect squares $\le n$ as $\lfloor\sqrt{n}\rfloor$, the number of tiles removed each operation.)6.EE.A.3Apply the properties of operations to generate equivalent expressions (Simplifying $k^2-k-(k-1)=k^2-2k+1=(k-1)^2$ to prove two operations turn $k^2$ tiles into $(k-1)^2$.)4.OA.C.5Generate a number or shape pattern following a given rule (Continuing the square-base pattern $10^2\to 9^2\to\cdots\to 1^2$ and counting $9\times 2=18$ operations.)
⭐ Only the tile count matters, and every two operations knock the perfect-square count down one step, so $10^2$ tiles need $9\times 2=18$ operations to reach a single tile.
⭐ Only the tile count matters, and every two operations knock the perfect-square count down one step, so $10^2$ tiles need $9\times 2=18$ operations to reach a single tile.
More like this
Same archetype — closest grade level first.