Problem 2007

Let $S$ be a finite set of positive integers such that there are exactly 2023 ordered pairs $(x, y) \in S \times S$ with $xy$ a perfect square.

Let us analyze the structure of $S$.

For any $x, y \in S$, $xy$ is a perfect square if and only if the product of their squarefree parts is a square. For each $x \in S$, write $x = d_x^2 s_x$, where $s_x$ is squarefree. Then $xy$ is a perfect square if and only if $s_x s_y$ is a square, i.e., $s_x = s_y$.

Thus, for each $t$ (squarefree), let $S_t = \{x \in S : s_x = t\}$. For $x \in S_t$ and $y \in S_t$, $xy$ is a perfect square. For $x \in S_t$, $y \in S_{t'}$ with $t \neq t'$, $xy$ is not a perfect square.

Let $a_i = |S_{t_i}|$ for the distinct squarefree parts $t_1, \dots, t_k$ that appear in $S$. Then the total number of ordered pairs $(x, y)$ with $xy$ a perfect square is $\sum_{i=1}^k a_i^2 = 2023$.

We are to show that $S$ contains at least four distinct elements such that none of their pairwise products is a perfect square. That is, we need to find four elements with distinct squarefree parts.

Suppose, for contradiction, that there do not exist four such elements. Then the number of distinct squarefree parts $k \leq 3$.

Let us consider all possible values of $k$.

Case 1: $k = 1$.
Then $S$ consists of numbers with the same squarefree part, so $a_1 = n$, $n^2 = 2023$, but $2023$ is not a perfect square. Contradiction.

Case 2: $k = 2$.
Then $a_1 + a_2 = n$, $a_1^2 + a_2^2 = 2023$.
Try all possible integer solutions:
Let $a_1 = m$, $a_2 = n - m$.
Then $m^2 + (n - m)^2 = 2023$.
But $m^2 + (n - m)^2 = 2m^2 - 2nm + n^2 = 2023$.
But $n = a_1 + a_2 \leq \sqrt{2023} + \sqrt{2023} < 90$.
Try small values:
Let $a_1 = a_2 = t$, then $2t^2 = 2023 \implies t^2 = 1011.5$, not integer.
Try $a_1 = t$, $a_2 = t+1$:
$t^2 + (t+1)^2 = 2t^2 + 2t + 1 = 2023 \implies 2t^2 + 2t - 2022 = 0 \implies t^2 + t - 1011 = 0$.
Discriminant: $1 + 4044 = 4045$, not a perfect square.
Try $a_1 = t$, $a_2 = t+2$:
$t^2 + (t+2)^2 = t^2 + t^2 + 4t + 4 = 2t^2 + 4t + 4 = 2023 \implies 2t^2 + 4t - 2019 = 0$.
$t^2 + 2t - 1009.5 = 0$.
No integer solution.
Try $a_1 = 44$, $a_2 = 1$: $44^2 + 1^2 = 1936 + 1 = 1937$.
Try $a_1 = 45$, $a_2 = 2$: $2025 + 4 = 2029$.
Try $a_1 = 44$, $a_2 = 5$: $1936 + 25 = 1961$.
Try $a_1 = 45$, $a_2 = 7$: $2025 + 49 = 2074$.
Try $a_1 = 40$, $a_2 = 13$: $1600 + 169 = 1769$.
Try $a_1 = 42$, $a_2 = 17$: $1764 + 289 = 2053$.
Try $a_1 = 43$, $a_2 = 14$: $1849 + 196 = 2045$.
Try $a_1 = 41$, $a_2 = 10$: $1681 + 100 = 1781$.
Try $a_1 = 45$, $a_2 = 14$: $2025 + 196 = 2221$.
So, no integer solution for $k = 2$.

Case 3: $k = 3$.
Let $a_1, a_2, a_3 \geq 1$, $a_1^2 + a_2^2 + a_3^2 = 2023$.
Try $a_1 = a_2 = a_3 = t$, $3t^2 = 2023 \implies t^2 = 674.33$.
Try $a_1 = a_2 = t$, $a_3 = t+1$:
$t^2 + t^2 + (t+1)^2 = 3t^2 + 2t + 1 = 2023 \implies 3t^2 + 2t - 2022 = 0$.
Discriminant: $4 + 3 \times 2022 \times 4 = 4 + 24264 = 24268$, not a perfect square.
Try $a_1 = t$, $a_2 = t+1$, $a_3 = t+2$:
$t^2 + (t+1)^2 + (t+2)^2 = t^2 + t^2 + 2t + 1 + t^2 + 4t + 4 = 3t^2 + 6t + 5 = 2023$.
$3t^2 + 6t - 2018 = 0$.
Discriminant: $36 + 3 \times 2018 \times 4 = 36 + 24216 = 24252$, not a perfect square.
Try $a_1 = 44$, $a_2 = 44$, $a_3 = 5$: $1936 + 1936 + 25 = 3897$.
Try $a_1 = 44$, $a_2 = 43$, $a_3 = 2$: $1936 + 1849 + 4 = 3789$.
Try $a_1 = 45$, $a_2 = 1$, $a_3 = 1$: $2025 + 1 + 1 = 2027$.
Try $a_1 = 44$, $a_2 = 5$, $a_3 = 2$: $1936 + 25 + 4 = 1965$.
Try $a_1 = 45$, $a_2 = 7$, $a_3 = 1$: $2025 + 49 + 1 = 2075$.
Try $a_1 = 42$, $a_2 = 17$, $a_3 = 2$: $1764 + 289 + 4 = 2057$.
Try $a_1 = 43$, $a_2 = 14$, $a_3 = 2$: $1849 + 196 + 4 = 2049$.
Try $a_1 = 41$, $a_2 = 10$, $a_3 = 2$: $1681 + 100 + 4 = 1785$.
Try $a_1 = 44$, $a_2 = 44$, $a_3 = 1$: $1936 + 1936 + 1 = 3873$.
Try $a_1 = 44$, $a_2 = 43$, $a_3 = 1$: $1936 + 1849 + 1 = 3786$.
Try $a_1 = 45$, $a_2 = 1$, $a_3 = 2$: $2025 + 1 + 4 = 2030$.
Try $a_1 = 44$, $a_2 = 5$, $a_3 = 1$: $1936 + 25 + 1 = 1962$.
Try $a_1 = 45$, $a_2 = 7$, $a_3 = 2$: $2025 + 49 + 4 = 2078$.
Try $a_1 = 42$, $a_2 = 17$, $a_3 = 1$: $1764 + 289 + 1 = 2054$.
Try $a_1 = 43$, $a_2 = 14$, $a_3 = 1$: $1849 + 196 + 1 = 2046$.
Try $a_1 = 41$, $a_2 = 10$, $a_3 = 1$: $1681 + 100 + 1 = 1782$.

So, there is no solution for $k = 3$ with positive integers $a_1, a_2, a_3$.

Therefore, the only possibility is $k \geq 4$.

Thus, there are at least four distinct squarefree parts among the elements of $S$. Pick one element from each of four different $S_{t_i}$, say $x_1, x_2, x_3, x_4$ with $s_{x_i}$ all distinct. Then for any $i \neq j$, $x_i x_j$ is not a perfect square, since $s_{x_i} \neq s_{x_j}$.

Therefore, there exist at least four distinct elements in $S$ such that none of their pairwise products is a perfect square, as desired.