2002 AMC 10A Problems/Problem 22

From AoPSWiki

Problem

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?

$\text{(A)}\ 10 \qquad \text{(B)}\ 11 \qquad \text{(C)}\ 18 \qquad \text{(D)}\ 19 \qquad \text{(E)}\ 20$

Solution

The pattern is quite simple to see after listing a couple of terms.

$\begin{tabular}{|r|r|r|}\hline\#&\text{Removed}&\text{Left}\\\hline1&10&90\\2&9&81\\3&9&72\\4&8&64\\5&8&56\\6&7&49\\7&7&42\\8&6&36\\9&6&30\\10&5&25\\11&5&20\\12&4&16\\13&4&12\\14&3&9\\15&3&6\\16&2&4\\17&2&2\\\boxed{18}&1&1\\\hline\end{tabular}$

Given $n^2$ tiles, a step removes $n$ tiles, leaving $n^2 - n$ tiles behind. Now, $(n-1)^2 = n^2 - n + (1-n) < n^2 - n < n^2$ , so in the next step $n-1$ tiles are removed. This gives $(n^2 - n) - (n-1) = n^2 - 2n + 1 = (n-1)^2$ , another perfect square.

Thus each two steps we cycle down a perfect square, and in $(10-1)\times 2 = 18$ steps, we are left with $1$ tile.

2002 AMC 10A (Problems)
Preceded by Problem 21	Followed by Problem 23
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25

Personal tools

Navigation

Search

Toolbox

2002 AMC 10A Problems/Problem 22

From AoPSWiki

Problem

Solution

See also