2023 INMO Problems/Problem 1
PROBLEM
Let S be a finite set of positive integers. Assume that there are precisely 2023 ordered pairs (x, y) in S × S so that the product xy is a perfect square. Prove that one can find at least four distinct elements in S so that none of their pairwise products is a perfect square. Note: As an example, if S = {1, 2, 4}, there are exactly five such ordered pairs: (1, 1), (1, 4), (2, 2), (4, 1), and (4, 4).
SOLUTION
To prove that there exist at least four distinct elements in such that none of their pairwise products is a perfect square, we can proceed as follows:
Each element in can be uniquely expressed as:
where:
is a positive integer.
is a square-free positive integer (i.e., has no square factors other than 1).
The square-free part of is . Two elements and in satisfy being a perfect square if and only if they have the same square-free part.
Based on the square-free parts, partition into disjoint classes:
where each consists of elements in that share the same square-free part.
The number of ordered pairs such that is a perfect square is:
where denotes the number of elements in class .
Using the Cauchy-Schwarz inequality:
Given , let . Then:
To maximize , should be as large as possible. However, even without knowing , we can infer that:
If , the inequality would impose a restriction on that makes it impossible to achieve exactly 2023 ordered pairs.
Therefore, .
Since there are at least four distinct classes, we can select one element from each of four different classes. Let these elements be . By construction:
and belong to different classes, so is not a perfect square.
Similarly, and , and , and , and , and are all in distinct classes, ensuring none of their pairwise products is a perfect square.
Thus, we have shown that there must exist at least four distinct elements in such that none of their pairwise products is a perfect square.
Because must contain elements from at least four distinct square-free classes, we can choose four different elements each from a separate class. Then none of their pairwise products is a square. Thus, such four distinct elements exist in .