We wrote the numbers from 1 to 2009 on a piece of paper. In the second step, we also wrote down twice each of these numbers on the paper, then erased the numbers that appeared twice. We repeat this step in such a way that in the $i$-th step, we also write down $i$ times each of the numbers $1, 2, \ldots, 2009$ on the paper, then erase the numbers that appear twice. How many numbers will be on the paper after the 2009th step?
Solution. The final result does not change if we do not delete anything step by step, but instead remove the numbers that appear an even number of times on the paper after the 2009th step. In the i-th step, we write the numbers $k i$ on the paper, where $1 \leq k \leq 2009$, and $1 \leq i \leq 2009$. Therefore, before any deletions, the numbers on the paper are exactly those that can be written as the product of two positive integers less than 2010. Among them, those will remain after the deletions that can be written in an odd number of ways (considering the order of the factors) as the product of two such integers. Notice that if $i \neq k$, then $i \cdot k$ and $k \cdot i$ are two different representations of the same number. From this, it is clear that the factorizations of the written numbers can be paired: the $i \cdot k$ and $k \cdot i$ representations will be pairs of each other. The $k \cdot k$ factorizations stand alone, and these are precisely the factorizations of the square numbers, each having exactly one. Therefore, the square numbers appear an odd number of times on the paper, while the others appear an even number of times. After the deletions, therefore, the numbers $1^{2}, 2^{2}, \ldots, 2009^{2}$ remain, a total of 2009 numbers.