6. What is the maximum number of natural numbers not exceeding 2016 that can be marked so that the product of any two marked numbers is a perfect square?
Answer: 44.

Solution. Let's find the number of natural numbers whose squares are no greater than 2016. There are 44 such numbers, since $44^{2}=1936 < 2016$. Since the product of two perfect squares is a perfect square, the numbers $1=1^{2}, 4=2^{2}, \ldots, 1936=44^{2}$ can be marked.

We will prove that it is impossible to mark a larger number of numbers. Indeed, consider the desired set of numbers and divide each number in this set by the largest perfect square that divides it. We will get a new set of numbers, and in the factorization of each of the resulting numbers into prime factors, these factors can only enter to the first power. Note that each prime factor (if it exists) must be present in all factorizations, since when multiplying any two numbers in the resulting set, it must end up in an even power. This means that after dividing each number in the desired set by the largest squares, we should get the same number $q$. If $q=1$, we get a set of 44 numbers that are perfect squares themselves (see above), and if $q>1$, we get a set of fewer numbers, since $1936 q > 2016$.

Grading Criteria

“+" - a complete and well-reasoned solution is provided

“士” - a generally correct reasoning is provided, containing minor gaps or inaccuracies

"Ғ" - only the correct answer and a correct example are provided

“-” - only the answer is provided

“-” - the problem is not solved or solved incorrectly