2002 AMC 10A Problem 22

P21-25~6 minPrint

Number Properties Games & Processes Use an invariant, parity, or coloring argument Compute small cases, spot the pattern, generalize

A 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?

Show solution without answering

Key insight

Starting from a square number of tiles, two rounds always bring you to the next smaller square: 100, 90, 81, then 72, 64, and so on.

Solution

After each round the tiles are renumbered $1, 2, 3, \ldots$ , so all that matters is how many tiles there are. With $N$ tiles, a round removes one tile for each perfect square from $1$ up to $N$ .

Run the first few rounds.

tiles at start	squares removed	tiles left
$100$	$1, 4, \ldots, 100$ : ten of them	$90$
$90$	$1, 4, \ldots, 81$ : nine	$81$
$81$	$1, 4, \ldots, 81$ : nine	$72$
$72$	$1, 4, \ldots, 64$ : eight	$64$
$64$	$1, 4, \ldots, 64$ : eight	$56$
$56$	$1, 4, \ldots, 49$ : seven	$49$

Spot the pattern. Every two rounds, the count goes from one square number to the next smaller one: $100 = 10^2$ , then $81 = 9^2$ , then $64 = 8^2$ , then $49 = 7^2$ .

Why it always happens. Start with $n \times n$ tiles. The first round removes $n$ tiles, leaving $n \times n - n$ . That number is below $n \times n$ but above $(n-1) \times (n-1)$ (for example $90$ is between $81$ and $100$ ). So the next round removes exactly $n - 1$ tiles, leaving $n \times n - n - (n - 1) = (n - 1) \times (n - 1)$ .

Check the very end. $4$ tiles: remove $1$ and $4$ , leaving $2$ . $2$ tiles: remove $1$ , leaving $1$ . So going from $2^2$ to $1^2$ also takes two rounds.

5. Count. To go from $10^2$ down to $1^2$ , the number being squared drops $10 \to 9 \to \cdots \to 1$ : that is $9$ drops, each taking $2$ rounds. So
$9 \times 2 = 18 \text{ rounds}.$

The answer is $\boxed{\textbf{(C)}\ 18}$ .

Why this works

For a process that repeats many times, work out the first few steps by hand and look for a pattern, then check that the pattern must keep going. Here the tile count is a perfect square after every second round, which makes counting easy. Always check the last step separately, since patterns sometimes change at the end.

Alternative approach

Just keep the table going. The numbers of tiles removed are
$10, 9, 9, 8, 8, 7, 7, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1,$
which add to $99$ , taking $100$ tiles down to $1$ . There are $18$ numbers in the list.

Concise solution

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

Only the number of tiles matters, since renumbering restores the set $\{1, \dots, N\}$ . With $N$ tiles, the operation deletes the $\lfloor \sqrt{N} \rfloor$ perfect squares up to $N$ .

Follow what happens starting from a perfect square, $N = n^2$ :

First operation: $n$ squares are removed, leaving $n^2 - n$ tiles.
Since $(n-1)^2 = n^2 - 2n + 1 < n^2 - n < n^2$ , the largest square not exceeding $n^2 - n$ is $(n-1)^2$ , so the second operation removes $n - 1$ tiles, leaving $n^2 - n - (n - 1) = n^2 - 2n + 1 = (n-1)^2$ .

So every two operations move from $n^2$ tiles to $(n-1)^2$ tiles. Starting at $100 = 10^2$ , reaching $1 = 1^2$ requires the nine transitions $10 \to 9 \to \dots \to 1$ , i.e. $2 \cdot 9 = 18$ operations.

Concretely: $100 \to 90 \to 81 \to 72 \to 64 \to 56 \to 49 \to \dots \to 4 \to 2 \to 1$ .

The answer is $\boxed{\textbf{(C)}\ 18}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics
Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
Introduction to Algebra, Chapter 20: Special Functions (§20.3)