Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2002 AMC 10A Problems/Problem 22"

m
(→‎Solution 3)
 
(4 intermediate revisions by 3 users not shown)
Line 4: Line 4:
 
<math>\text{(A)}\ 10 \qquad \text{(B)}\ 11 \qquad \text{(C)}\ 18 \qquad \text{(D)}\ 19 \qquad \text{(E)}\ 20</math>
 
<math>\text{(A)}\ 10 \qquad \text{(B)}\ 11 \qquad \text{(C)}\ 18 \qquad \text{(D)}\ 19 \qquad \text{(E)}\ 20</math>
  
−
== Solution ==
+
==Solution 1==
−
===Solution 1===
 
 
The pattern is quite simple to see after listing a couple of terms.
 
The pattern is quite simple to see after listing a couple of terms.
  
Line 30: Line 29:
 
17&2&2\\
 
17&2&2\\
 
18&1&1\\
 
18&1&1\\
 +
 +
 +
 +
 
\hline
 
\hline
 
\end{tabular} </cmath>
 
\end{tabular} </cmath>
 +
 
Thus, the answer is <math>\boxed{\text{(C) } 18}</math>.
 
Thus, the answer is <math>\boxed{\text{(C) } 18}</math>.
  
−
===Solution 2===
+
==Solution 2==
 
Given <math>n^2</math> tiles, a step removes <math>n</math> tiles, leaving <math>n^2 - n</math> tiles behind. Now, <math>(n-1)^2 = n^2 - n + (1-n) < n^2 - n < n^2</math>, so in the next step <math>n-1</math> tiles are removed. This gives <math>(n^2 - n) - (n-1) = n^2 - 2n + 1 = (n-1)^2</math>, another perfect square.
 
Given <math>n^2</math> tiles, a step removes <math>n</math> tiles, leaving <math>n^2 - n</math> tiles behind. Now, <math>(n-1)^2 = n^2 - n + (1-n) < n^2 - n < n^2</math>, so in the next step <math>n-1</math> tiles are removed. This gives <math>(n^2 - n) - (n-1) = n^2 - 2n + 1 = (n-1)^2</math>, another perfect square.
  
 
Thus each two steps we cycle down a perfect square, and in <math>(10-1)\times 2 = 18</math> steps, we are left with <math>1</math> tile, hence our answer is <math>\boxed{\text{(C) } 18}</math>.
 
Thus each two steps we cycle down a perfect square, and in <math>(10-1)\times 2 = 18</math> steps, we are left with <math>1</math> tile, hence our answer is <math>\boxed{\text{(C) } 18}</math>.
 +
 +
== Solution 3 ==
 +
 +
We start of with <math>100 = 10 \cdot 10</math> numbers. When we use the certain operation, call if <math>P(x)</math>, have <math>100 - 10 = 90 = 10 \cdot 9</math>.
 +
Then we do <math>P(x)</math> again, to subtract <math>9</math> numbers and get <math>9 \cdot 9</math>. In the end, we will want <math>1 = 1 \cdot 1</math>. We can say we have to use <math>P(x)</math> once to make <math>n \cdot n</math> into <math>n \cdot (n-1)</math>. Thus we must use it twice to get from <math>n \cdot n</math> to <math>(n-1)(n-1)</math>. For example, it takes us <math>2</math> of <math>P(x)</math> to get from <math>10 \cdot 10</math> to <math>9 \cdot 9</math>. Then <math>2</math> of <math>P(x)</math> to get from <math>9 \cdot 9</math> to <math>8 \cdot 8</math>. You should try this with <math>7</math> and <math>6</math>, and see it works. This means we can have <math>n</math> be the number we start with, and <math>1</math> be the number we want. Then we would use <math>P(x)</math>, <math>2(n - 1)</math> times to get <math>1 \cdot 1</math>. Substituting <math>n</math> for <math>10</math> we get <math>2(10-1) = 2 \cdot 9 = \boxed{18}</math>.
 +
- Wiselion
 +
 +
== Video Solution ==
 +
 +
https://www.youtube.com/watch?v=CuKko0JpIdQ  ~David
  
 
== See also ==
 
== See also ==

Latest revision as of 22:13, 13 September 2023

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 1

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

\[\begin{tabular}{|r|r|r|} \hline \#&\text{Removed}&\text{Left}\\ \hline 1&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\\ 18&1&1\\ \hline \end{tabular}\]

Thus, the answer is $\boxed{\text{(C) } 18}$.

Solution 2

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, hence our answer is $\boxed{\text{(C) } 18}$.

Solution 3

We start of with $100 = 10 \cdot 10$ numbers. When we use the certain operation, call if $P(x)$, have $100 - 10 = 90 = 10 \cdot 9$. Then we do $P(x)$ again, to subtract $9$ numbers and get $9 \cdot 9$. In the end, we will want $1 = 1 \cdot 1$. We can say we have to use $P(x)$ once to make $n \cdot n$ into $n \cdot (n-1)$. Thus we must use it twice to get from $n \cdot n$ to $(n-1)(n-1)$. For example, it takes us $2$ of $P(x)$ to get from $10 \cdot 10$ to $9 \cdot 9$. Then $2$ of $P(x)$ to get from $9 \cdot 9$ to $8 \cdot 8$. You should try this with $7$ and $6$, and see it works. This means we can have $n$ be the number we start with, and $1$ be the number we want. Then we would use $P(x)$, $2(n - 1)$ times to get $1 \cdot 1$. Substituting $n$ for $10$ we get $2(10-1) = 2 \cdot 9 = \boxed{18}$. - Wiselion

Video Solution

https://www.youtube.com/watch?v=CuKko0JpIdQ ~David

See also

2002 AMC 10A (Problems • Answer Key • Resources)
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
All AMC 10 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_AMC_10A_Problems/Problem_22&oldid=198183"