
3. There are numbers $1,2, \ldots, 33$ written on the blackboard. In one step we choose a group of numbers on the blackboard (at least two) such that their product is a square, we erase them and write the square root of their product instead. We proceed until no group can be chosen. What is the least amount of numbers left on the blackboard?


Solution. The product of all the numbers written on the blackboard is

$$
S=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 .
$$

Apparently, the numbers $17,19,23,29$, and 31 can never be erased and can never be a part of any change. In any step, there is always left at least one other number, which gives in total $5+1=6$ numbers. Six numbers on the blackboard are achievable indeed: because of the odd exponents of primes 2, 3, 5, and 11 in $S$ we allocate the set $A=\{2,9,11,22,25\}$ and we put all the other numbers with exception of 17,19 , 23, 29 a 31 into set

$$
B=\{3,4,5,6,7,8,10,12,13,14,15,16,18,20,21,24,26,27,28,30,32,33\} .
$$

In the first step we choose the group $A$ and replace it by the number

$$
n=\sqrt{2 \cdot 9 \cdot 11 \cdot 22 \cdot 25}=\sqrt{2^{2} \cdot 3^{2} \cdot 5^{2} \cdot 11^{2}}=2 \cdot 3 \cdot 5 \cdot 11 .
$$

Because the product of all the numbers from $B$ is $2^{31-2} \cdot 3^{15-2} \cdot 5^{7-2} \cdot 7^{4} \cdot 11^{3-2}$. $13^{2}=2^{29} \cdot 3^{13} \cdot 5^{5} \cdot 7^{4} \cdot 11 \cdot 13^{2}$, in the second step we choose $n$ together with all the numbers from $B$ and replace it by

$$
\sqrt{(2 \cdot 3 \cdot 5 \cdot 11) \cdot\left(2^{29} \cdot 3^{13} \cdot 5^{5} \cdot 7^{4} \cdot 11 \cdot 13^{2}\right)}=2^{15} \cdot 3^{7} \cdot 5^{3} \cdot 7^{2} \cdot 11 \cdot 13,
$$

which leaves just six numbers on the blackboard.

Conclusion. The sought least amount is six.

## Second Round of the 59th Czech and Slovak Mathematical Olympiad (January 20th, 2010)

![](https://cdn.mathpix.com/cropped/2024_04_17_10b455106c778bb0ba10g-11.jpg?height=161&width=390&top_left_y=323&top_left_x=515)
