Difference between revisions of "2023 INMO Problems/Problem 1"
Combi-hater (talk | contribs) (→SOLUTION) |
Flaringrain (talk | contribs) (→PROBLEM) |
||
Line 7: | Line 7: | ||
(2, 2), (4, 1), and (4, 4). | (2, 2), (4, 1), and (4, 4). | ||
− | ==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 11: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 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 .