3. On the board, the numbers $1,2, \ldots, 33$ are written. In one step, we choose several numbers written on the board (at least two), whose product is a square of a natural number, erase the chosen numbers, and write the square root of their product on the board. We continue this process until only such numbers remain on the board that the product of any of them is not a square. What is the minimum number of numbers that can remain on the board?

The written part of the school round in category A takes place

on Tuesday, December 1, 2009

so that it starts in the morning and the contestants have 4 hours of pure time to solve the problems. For each problem, a contestant can earn 6 points, and a successful solver is a student who scores 10 points or more. Allowed aids are writing and drawing supplies, school MF tables, and calculators without a graphical display. These details will be communicated to the students before the start of the competition.

## Solutions to the written part of the school round in category $A$
3. The product of all numbers written on the board is equal to

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

The presence of odd exponents means that $S$ is not a perfect square. Therefore, we cannot erase all the numbers in the first step, and the prime numbers 17, 19, 23, 29, and 31 will never be erased. From all the other numbers that can participate in the modifications, a non-empty set of numbers will always be formed, so there will always be at least $5+1=6$ numbers on the board. We will show that 6 is the smallest possible number by describing one of the possible procedures.

Due to the odd exponents of the prime numbers $2, 3, 5$, and 11, we first select the group of numbers $A=\{2,9,11,22,25\}$ and place all other numbers different from 17, 19, 23, 29, and 31 into the group

$$
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 select all numbers from $A$ and replace them with 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 .
$$

Since the product of all numbers in $B$ is $2^{31-2} \cdot 3^{15-2} \cdot 5^{7-2} \cdot 7^{4} \cdot 11^{3-2} \cdot 13^{2}=2^{29} \cdot 3^{13} \cdot 5^{5} \cdot 7^{4} \cdot 11 \cdot 13^{2}$, in the second step, we select the number $n$ along with all numbers from $B$ and replace them with the number

$$
\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
$$

Then, only six numbers will remain on the board, which, as we have explained, is the smallest possible number.

For a complete solution, award 6 points, of which 1 point for the consideration of the prime numbers 17, 19, 23, 29, and 31, 2 points for identifying the odd exponents of the prime numbers 2, 3, 5, and 11, and 3 points for describing the procedure leading to the target six numbers (the sixth number different from 17, 19, 23, 29, and 31 may vary depending on different procedures).