
3. There are numbers 1,2,.., 33 written on a blackboard. In one step we choose two numbers on the blackboard such that one of them divides the other one, we erase the two numbers and write their integer quotient instead. We proceed in this manner until no number on the blackboard divides another one. What is the least possible amount of numbers left on the blackboard?


Solution. In the process, apparently only numbers from the set $M=\{1,2, \ldots, 33\}$ can be on the blackboard. Prime numbers 17, 19,23, 29 a 31 are going to stay on the blackboard, in one copy each, because they have no other divisor than the number 1 and the set $M$ does not contain any other of their multiples.

We explain now, why there must always be two other numbers on the blackboard. the product of all numbers is

$$
S=33 !=2^{31} \cdot 3^{15} \cdot 5^{7} \cdot 7^{4} \cdot 11^{3} \cdot 13^{2} \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31
$$

at the beginning.

In each step we choose a pair $(x, y)$ with $x \mid y$, that is numbers of the form $x=a, y=k a$ and we replace them with the number $y / x=k$. the product $S$ of all the numbers on the blackboard changes to the new value $S / a^{2}$. It is evident, that the parity of the exponent of each prime number divisor in the prime number factorization of $S$ is preserved. Especially the four primes 2, 3, 5, and 11 divide the product $S$ throughout the process. Since $2 \cdot 3 \cdot 5 \cdot 11>33$ it follows that on the table there always must be at least two numbers which product is divisible by $2 \cdot 3 \cdot 5 \cdot 11$. On the whole, there must always be at least seven numbers on the blackboard.

The sequence of steps

$$
\begin{gathered}
32,16 \rightarrow 2, \quad 30,15 \rightarrow 2, \quad 28,14 \rightarrow 2, \quad 26,13 \rightarrow 2, \quad 24,12 \rightarrow 2, \quad 22,11 \rightarrow 2 \\
27,9 \rightarrow 3, \quad 21,7 \rightarrow 3, \quad 18,6 \rightarrow 3, \quad 25,5 \rightarrow 5, \quad 20,4 \rightarrow 5, \quad 8,2 \rightarrow 4 \\
5,5 \rightarrow 1, \quad 4,2 \rightarrow 2, \quad 3,3 \rightarrow 1, \quad 3,3 \rightarrow 1, \quad 2,2 \rightarrow 1, \quad 2,2 \rightarrow 1, \quad 2,2 \rightarrow 1
\end{gathered}
$$

leaves numbers $17,19,23,29,31,10,33$, and seven numbers 1 on the blackboard. The 1s can be eliminated in seven further steps, which leaves just seven numbers on the blackboard.

Conclusion: the least amount of numbers which can be left on the blackboard is seven.
