Skip to main content

2002 AMC 10A Problem 22

Problem 22 of 25HarderAlgebraNumber Theory

A set of tiles numbered 11 through 100100 is modified repeatedly by the following operation: remove all tiles numbered with a perfect square, and renumber the remaining tiles consecutively starting with 1.1. How many times must the operation be performed to reduce the number of tiles in the set to one?

Answer choices

Show solution

Solution

Starting from n2n^2 tiles, one operation removes the nn perfect squares, leaving n2−n.n^2-n. The next operation removes n−1n-1 perfect squares, leaving n2−n−(n−1)=(n−1)2.n^2-n-(n-1)=(n-1)^2. So every two operations reduce n2n^2 to (n−1)2.(n-1)^2. Going from 102=10010^2=100 down to 12=11^2=1 takes 2(10−1)=182(10-1)=18 operations. Thus, the correct answer is C.

More practice

Concepts: perfect square · recursion · pattern recognition

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.