XXIX Rioplatense Mathematical Olympiad

For each $m\in \mathbb{N}$, let $f(m)$ be the product of the primes that appear with odd exponent in the prime factorization of $m$. It is easy to see that given two positive integers $a$ and $b$, the product $ab$ is a perfect square if and only if $f(a)=f(b)$.

For each $k\in \mathbb{N}$, let $S$ be the set of all $m$ in $\{1,2,\dots ,4n\}$ such that $f(m)=k$. Note that if $k$ is not squarefree, then $S$ is empty. Also, as $f(m)\le m$ for all $m$, we have that each element of $\{1,2,\dots ,4n\}$ belongs to exactly one of the sets $S_1,S_2,\dots ,S_{4n}$.

By the initial observation each of the pairs that we are going to form must be integrated by two elements of the same $S_j$; furthermore, any way of assembling the pairs respecting that rule meets the conditions of the statement. Then, if each set $S_j$ has $a_j$ elements, the maximum number of pairs that can be formed is $\lfloor \frac{a_1}{2}\rfloor +\lfloor \frac{a_2}{2}\rfloor +\cdots +\lfloor \frac{a_{4n}}{2}\rfloor$.

We claim that $\lfloor \frac{a_j}{2}\rfloor$ is equal to the number of multiples of $4$ in $S_j$. Indeed, this is obvious if $S_j$ is empty; if instead $j$ is squarefree, the elements of $S_j$ are the numbers of the form $j\cdot s^2$ with $s$ covering the values from $1$ to $a_j$. Since $j$ is squarefree, it has at most one factor of $2$, so $j\cdot s^2$ is a multiple of $4$ if and only if $s$ is even. Then, the number of multiples of $4$ in $S_j$ coincides with the number of even numbers between $1$ and $a_j$, which is precisely $\lfloor \frac{a_j}{2}\rfloor$.

From the above, the sum $\lfloor \frac{a_1}{2}\rfloor +\lfloor \frac{a_2}{2}\rfloor +\cdots +\lfloor \frac{a_{4n}}{2}\rfloor$ matches the number of multiples of $4$ among all the sets $S_1,S_2,\dots ,S_{4n}$, that is, the number of multiples of $4$ in $\{1,2,\dots ,4n\}$. This quantity is $n$, and that is the answer to the problem.