, 2018

For convenience, let us call integers that are not perfect squares "good" and integers that are perfect squares "bad". We shall prove the given estimation by induction.

Indeed,

For $n=1$ we only have 1 square-free partition.

For $n=2$ we have four numbers $x_{1}, x_{2}, y_{1}, y_{2}$ with $x_{1}y_{1}$ and $x_{2}y_{2}$ are good. Since $x_{1}^{2} = \frac{x_{1}x_{2} \cdot x_{1}y_{2}}{x_{2}y_{2}}$ and the number $x_{2}y_{2}$ is good, then two numbers $x_{1}x_{2}, x_{1}y_{2}$ cannot be both bad. We have some cases:

- If $x_{1}x_{2}, x_{1}y_{2}$ are both good, then we have two subcases: if $x_{2}y_{1}$ is good, then we are done; otherwise, consider the ratio $y_{1}y_{2} = \frac{x_{2}y_{1} \cdot x_{2}y_{2}}{x_{2}^{2}}$, then this number must be good, so the other partition $\left(x_{1}, x_{2}\right), \left(y_{1}, y_{2}\right)$ is square-free.

- Otherwise, assume that $x_{1}x_{2}$ is bad and $x_{1}y_{2}$ is good. By a similar argument, we have the partition $\left(x_{1}, y_{2}\right), \left(x_{2}, y_{1}\right)$.

So in all cases, we always have one more partition, the statement is true for $n=2$.

Suppose that for some $n \geq 2$, the statement is true. Consider $2n+2$ numbers with one square-free partition
$$\left(x_{1}, y_{1}\right), \left(x_{2}, y_{2}\right), \ldots, \left(x_{n+1}, y_{n+1}\right),$$
First, fix the pair $(x_{1}, y_{1})$ then apply the induction hypothesis for the other $n$ pairs, we have $n!$ square-free partitions. After that, take some index $2 \leq k \leq n+1$, then change four numbers $x_{1}, y_{1}, x_{k}, y_{k}$ to another partition; so for $2(n-1)$ other pairs, we have at least $(n-1)!$ square-free partitions. In total, we get at least
$$n! + n \cdot (n-1)! = (n+1)! \text{ square-free partitions. }$$
Hence, the statement is also true for $n+1$. This finishes our proof.

Remark. We can show an example that satisfies the equality as: $p, p^{2}, p^{3}, \ldots, p^{n}$. We just can make pairs of different parity exponents. $\square$