The partition of $2n$ positive integers into $n$ pairs is called square-free if the product of numbers in each pair is not a perfect square.Prove that if for $2n$ distinct positive integers, there exists one square-free partition, then there exists at least $n!$ square-free partitions.
Problem
Source: 2018 Saudi Arabia BMO TST I p3
Tags: combinatorics, partition
Diamond-jumper76
18.01.2025 20:52
For convenience, let integers that are not perfect squares be called "good" and integers that are perfect squares be called "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_1y_1 \) and \( x_2y_2 \) good. Since
$$
x_1^2 = \frac{x_2x_1y_2}{y_1}
$$and the number \( x_2y_2 \) is good, then two numbers \( x_1x_2 \), \( x_1y_1 \) cannot both be bad. We have some cases:
1. If \( x_1x_2 \) and \( y_2 \) are both good, then we have two sub-cases:
- If \( x_1y_1 \) is good, then one partition is \( (x_1, y_1) \), \( (x_2, y_2) \), which is square-free.
- Otherwise, assume the ratio
$$
y_1y_2 = \frac{x_1y_2}{x_2y_1}
$$is good. Then this number must be good, and the other partition \( (x_1, x_2) \), \( (y_1, y_2) \) is square-free.
2. Otherwise, assume \( x_1x_2 \) is bad and \( x_1y_2 \) is good. By similar arguments, we have the partition \( (x_1, y_1) \), \( (x_2, y_2) \).
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:
$$
(x_1, y_1), (x_2, y_2), \dots, (x_{n+1}, y_{n+1}).
$$
First, fix the pair \( (x_1, y_1) \), then apply the induction hypothesis for other \( n \) pairs. We now 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)!
$$square-free partitions.
Hence, the statement is also true for \( n + 1 \). This finishes our proof.
RemarkWe can show an example that satisfies the equality as \( p, p^2, p^3, \dots, p^{n+1} \). We just make pairs of different parity exponents.
instead of calling good and bad, we can construct a graph with the numbers as vertices and the edge is connected iff the product is a square.
we notice that if two sides of a triangle are connected then the third one as well.
also we notice that if the graph has $2n$ vertices and have a complete subgraph of $n+1$ vertices then there is no such a partition from the pigeonhole principle.
now for the induction we make two cases for a vertex A:
Case1: A has degree $\geq n$ then from the above claims there are no partitions and hence a contradiction
Case2 (always true): A has a degree less than $n$ which means there are at least $n$ other vertices such that A can be paired with and foe each one we have $(n-1)!$ so the total is $n!$