2002 AMC 10A Problem 22

Question

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?

10

11

18

19

20

Answer: C

Concepts:perfect square recursion pattern recognition

Difficulty rating: 1790

Small hint:

Removing the perfect squares from

n^2

tiles leaves

n^2-n

tiles

Big hint:

Two operations take

n^2

tiles down to

(n-1)^2

Solution:

Starting from

n^2

tiles, one operation removes the

n

perfect squares, leaving

n^2-n.

The next operation removes

n-1

perfect squares, leaving

n^2-n-(n-1)=(n-1)^2.

So every two operations reduce

n^2

to

(n-1)^2.

Going from

10^2=100

down to

1^2=1

takes

2(10-1)=18

operations.

Thus, the correct answer is C.