Team selection tests for BMO 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\ge 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),\dots ,\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\le k\le 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,\dots ,p^n$. We just can make pairs of different parity exponents. $\square$