Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 INMO Problems/Problem 1"

(Created page with "==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 t...")
 
(→‎PROBLEM)
 
(One intermediate revision by one other user not shown)
Line 8: Line 8:
  
 
==SOLUTION==
 
==SOLUTION==
 +
 +
To prove that there exist at least four distinct elements in <math>S</math> such that none of their pairwise products is a perfect square, we can proceed as follows:
 +
 +
Each element <math>x</math> in <math>S</math> can be uniquely expressed as:
 +
 +
<math>x = a^2 \cdot b</math>
 +
 +
where:
 +
 +
<math>a</math> is a positive integer.
 +
 +
<math>b</math> is a square-free positive integer (i.e., <math>b</math> has no square factors other than 1).
 +
 +
The square-free part of <math>x</math> is <math>b</math>. Two elements <math>x</math> and <math>y</math> in <math>S</math> satisfy <math>xy</math> being a perfect square if and only if they have the same square-free part.
 +
 +
Based on the square-free parts, partition <math>S</math> into disjoint classes:
 +
 +
<math>S = C_1 \cup C_2 \cup \dots \cup C_m</math>
 +
 +
where each <math>C_i</math> consists of elements in <math>S</math> that share the same square-free part.
 +
 +
The number of ordered pairs <math>(x, y)</math> such that <math>xy</math> is a perfect square is:
 +
 +
<math>\sum_{i=1}^{m} |C_i|^2 = 2023</math>
 +
 +
where <math>|C_i|</math> denotes the number of elements in class <math>C_i</math>.
 +
 +
Using the Cauchy-Schwarz inequality:
 +
 +
<math>\sum_{i=1}^{m} |C_i|^2 \geq \frac{(\sum_{i=1}^{m} |C_i|)^2}{m}</math>
 +
 +
Given <math>\sum |C_i|^2 = 2023</math>, let <math>n = |S|</math>. Then:
 +
 +
<math>2023 \geq \frac{n^2}{m} \implies m \geq \frac{n^2}{2023}</math>
 +
 +
To maximize <math>m</math>, <math>n</math> should be as large as possible. However, even without knowing <math>n</math>, we can infer that:
 +
 +
If <math>m \leq 3</math>, the inequality would impose a restriction on <math>n</math> that makes it impossible to achieve exactly 2023 ordered pairs.
 +
 +
Therefore, <math>m \geq 4</math>.
 +
 +
Since there are at least four distinct classes, we can select one element from each of four different classes. Let these elements be <math>a, b, c, d</math>. By construction:
 +
 +
<math>a</math> and <math>b</math> belong to different classes, so <math>ab</math> is not a perfect square.
 +
 +
Similarly, <math>a</math> and <math>c</math>, <math>a</math> and <math>d</math>, <math>b</math> and <math>c</math>, <math>b</math> and <math>d</math>, <math>c</math> and <math>d</math> 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 <math>S</math> such that none of their pairwise products is a perfect square.
 +
 +
Because <math>S</math> 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 <math>S</math>.

Latest revision as of 12:08, 1 October 2024

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_INMO_Problems/Problem_1&oldid=228728"