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 $S$ such that none of their pairwise products is a perfect square, we can proceed as follows:

Each element $x$ in $S$ can be uniquely expressed as:

$x = a^2 \cdot b$

where:

$a$ is a positive integer.

$b$ is a square-free positive integer (i.e., $b$ has no square factors other than 1).

The square-free part of $x$ is $b$ . Two elements $x$ and $y$ in $S$ satisfy $xy$ being a perfect square if and only if they have the same square-free part.

Based on the square-free parts, partition $S$ into disjoint classes:

$S = C_1 \cup C_2 \cup \dots \cup C_m$

where each $C_i$ consists of elements in $S$ that share the same square-free part.

The number of ordered pairs $(x, y)$ such that $xy$ is a perfect square is:

$\sum_{i=1}^{m} |C_i|^2 = 2023$

where $|C_i|$ denotes the number of elements in class $C_i$ .

Using the Cauchy-Schwarz inequality:

$\sum_{i=1}^{m} |C_i|^2 \geq \frac{(\sum_{i=1}^{m} |C_i|)^2}{m}$

Given $\sum |C_i|^2 = 2023$ , let $n = |S|$ . Then:

$2023 \geq \frac{n^2}{m} \implies m \geq \frac{n^2}{2023}$

To maximize $m$ , $n$ should be as large as possible. However, even without knowing $n$ , we can infer that:

If $m \leq 3$ , the inequality would impose a restriction on $n$ that makes it impossible to achieve exactly 2023 ordered pairs.

Therefore, $m \geq 4$ .

Since there are at least four distinct classes, we can select one element from each of four different classes. Let these elements be $a, b, c, d$ . By construction:

$a$ and $b$ belong to different classes, so $ab$ is not a perfect square.

Similarly, $a$ and $c$ , $a$ and $d$ , $b$ and $c$ , $b$ and $d$ , $c$ and $d$ 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 $S$ such that none of their pairwise products is a perfect square.

Because $S$ 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 $S$ .

Page

Toolbox

Search

2023 INMO Problems/Problem 1

PROBLEM

SOLUTION