Difference between revisions of "2021 IMO Problems/Problem 1"
Mathhyhyhy (talk | contribs) (→Solution 2) |
(→Solution 3) |
||
(18 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem== | + | == Problem == |
− | Let <math>n \ | + | Let <math>n \geq 100</math> be an integer. Ivan writes the numbers <math>n, n+1, \ldots, 2 n</math> each on different cards. He then shuffles these <math>n+1</math> cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square. |
− | ==Video Solutions== | + | == Video Solutions == |
https://youtu.be/cI9p-Z4-Sc8 [Video contains solutions to all day 1 problems] | https://youtu.be/cI9p-Z4-Sc8 [Video contains solutions to all day 1 problems] | ||
Line 9: | Line 9: | ||
https://www.youtube.com/watch?v=a3L9O7b1WYg [disclaimer: only a sketch of the solution] | https://www.youtube.com/watch?v=a3L9O7b1WYg [disclaimer: only a sketch of the solution] | ||
− | ==Solution 1== | + | == Solution 1 == |
− | |||
If we can guarantee that there exist <math>3</math> cards such that every pair of them sum to a perfect square, then we can guarantee that one of the piles contains <math>2</math> cards that sum to a perfect square. Assume the perfect squares <math>p^2</math>, <math>q^2</math>, and <math>r^2</math> satisfy the following system of equations: | If we can guarantee that there exist <math>3</math> cards such that every pair of them sum to a perfect square, then we can guarantee that one of the piles contains <math>2</math> cards that sum to a perfect square. Assume the perfect squares <math>p^2</math>, <math>q^2</math>, and <math>r^2</math> satisfy the following system of equations: | ||
<cmath>\usepackage{amsmath} | <cmath>\usepackage{amsmath} | ||
Line 43: | Line 42: | ||
~Mathdreams | ~Mathdreams | ||
− | ==Solution 2== | + | == Solution 2 == |
+ | For the statement to be true, there must be at least three pairs whose sum is each a perfect square. There must be p,q,r such that | ||
− | + | <math>p+q = x^2</math> and <math>q+r = y^2</math>, <math>p+r = z^2</math>. | |
− | + | WLOG <math>n \le p \le q \le r \le 2n </math> ... Equation <math>1</math> | |
− | + | <math>p = \frac{(x^2 + z^2 – y^2)}{2}</math> | |
− | + | <math>q = \frac{(x^2 + y^2 – z^2)}{2}</math> | |
− | q = (x^2 + y^2 – z^2) / | + | <math>r = \frac{(y^2 + z^2 – x^2)}{2}</math> |
− | r = (y^2 + z^2 – x^2) / | ||
by equation 1 | by equation 1 | ||
− | 2n | + | <math>2n \le x^2 + z^2 – y^2 \le 4n</math> ...(1) |
− | 2n | + | <math>2n \le x^2 + y^2 – z^2 \le 4n</math> ...(2) |
− | 2n | + | <math>2n \le y^2 + z^2 – z^2 \le 4n</math> ...(3) |
+ | if we add (2) and (3) to (1), | ||
− | + | (1) + (2) + (3) <math>\Rightarrow</math> | |
− | |||
− | + | <math>6n \le x^2 + y^2 + z^2 \le 12n</math> | |
− | |||
− | + | if we assume that x, y, and z is close enough, | |
− | + | <math>6n \le 3x^2 \le 12n</math> | |
+ | <math>2n \le x^2 \le 4n</math> | ||
+ | <math>\sqrt{(2n)} \le x \le 2\sqrt{n}</math> | ||
− | + | At this time <math>100 \le n</math>, so let's put <math>n = 100</math> to this | |
− | 15 | + | |
+ | <math>10\sqrt{2} \le (x,y,z) \le 20</math> | ||
+ | <math>15 \le (x,y,z) \le 20</math> | ||
where | where | ||
− | 2|x^2 + y^2 | + | <math>2|x^2 + y^2 - z^2</math> |
+ | <math>2|x^2 + z^2 - y^2</math> | ||
+ | <math>2|y^2 + z^2 - z^2</math> | ||
+ | |||
+ | <math>x = 16, y = 18, z = 20</math> fits perfectly | ||
+ | |||
+ | therefore the minimum of <math>n</math> fits the proposition so the proposition is true | ||
− | + | ~Mathhyhyhy | |
− | + | ~Kingfireboy | |
− | + | == Solution 3 == | |
− | + | Claim: If <math>n \geq 100</math>, then there exist at least three perfect squares between <math>n/2 + 1</math> and <math>n + 1</math> inclusive. | |
− | + | Proof: If <math>100 \leq n \leq 125</math>, then the perfect squares <math>64</math>, <math>81</math>, and <math>100</math> are between <math>n/2 + 1</math> and <math>n + 1</math>. | |
+ | |||
+ | What if <math>n \geq 126</math>? Let <math>f(t) = \sqrt{t + 1} - \sqrt{t/2 + 1}</math>. Note that | ||
+ | |||
+ | <cmath> f(126) = \sqrt{127} - \sqrt{64} > 11 - 8 = 3. </cmath> | ||
+ | |||
+ | Moreover, <math>f</math> is increasing because | ||
+ | |||
+ | <cmath>f'(t) = \frac{1}{\sqrt{4t + 4}} - \frac{1}{\sqrt{8t + 16}} > 0.</cmath> | ||
+ | |||
+ | So <math>f(n) \geq f(126) > 3</math>. Thus there are at least three distinct integers between <math>\sqrt{n/2 + 1}</math> and <math>\sqrt{n + 1}</math>, and their squares will lie between <math>n/2 + 1</math> and <math>n + 1</math>. This proves the claim. | ||
+ | |||
+ | Now given any <math>n \geq 100</math>, it follows from the claim that there exist three consecutive squares <math>(k - 1)^2</math>, <math>k^2</math>, and <math>(k + 1)^2</math> such that | ||
+ | |||
+ | <cmath>\frac{n}{2} + 1 \leq (k - 1)^2, k^2, (k + 1)^2 \leq n + 1,</cmath> | ||
+ | |||
+ | and therefore | ||
+ | |||
+ | <cmath>n \leq 2k^2 - 4k, 2k^2 + 1, 2k^2 + 4k \leq 2n.</cmath> | ||
+ | |||
+ | The three numbers <math>2k^2 - 4k</math>, <math>2k^2 + 1</math>, and <math>2k^2 + 4k</math> have the property that the sum of any two of them is a perfect square: | ||
+ | |||
+ | \begin{align*} | ||
+ | (2k^2 - 4k) + (2k^2 + 1) &= (2k - 1)^2, \\ | ||
+ | (2k^2 - 4k) + (2k^2 + 4k) &= (2k)^2, \\ | ||
+ | (2k^2 + 1) + (2k^2 + 4k) &= (2k + 1)^2. | ||
+ | \end{align*} | ||
+ | |||
+ | By the pigeonhole principle, cards showing two of these numbers will end up in the same pile, and the sum of those cards’ numbers will be a perfect square. | ||
+ | |||
+ | == See also == | ||
+ | {{IMO box|year=2021|before=First Problem|num-a=2}} | ||
+ | |||
+ | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 05:11, 4 June 2024
Problem
Let be an integer. Ivan writes the numbers
each on different cards. He then shuffles these
cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square.
Video Solutions
https://youtu.be/cI9p-Z4-Sc8 [Video contains solutions to all day 1 problems]
https://www.youtube.com/watch?v=a3L9O7b1WYg [disclaimer: only a sketch of the solution]
Solution 1
If we can guarantee that there exist cards such that every pair of them sum to a perfect square, then we can guarantee that one of the piles contains
cards that sum to a perfect square. Assume the perfect squares
,
, and
satisfy the following system of equations:
where
,
, and
are numbers on three of the cards. Solving for
,
, and
in terms of
,
, and
tells us that
,
, and
. We can then substitute
,
, and
to cancel out the
s in the denominatior, and simplifying gives
,
, and
. Now, we have to prove that there exists three numbers in these forms between
and
when
. Notice that
will always be the least of the three and
will always be the greatest of the three. So it is sufficient to prove that there exists numbers in the form
and
between
and
.
For two numbers in the form of and
to be between
and
, the inequalities
must be satisfied. We can then expand and simplify to get that
Then, we can complete the square on the left sides of both inequalities and isolate
to get that
Notice that
must be an integer, so there must be an integer between
and
. If
and
differ by at least
, then we can guarantee that there is an integer between them (and those integers are the possible values of
). Setting up the inequality
and solving for
tells us that
always works. Testing the remaining
numbers (
to
) manually tells us that there is an integer between
and
when
. Therefore, there exists a triplet of integers
with
when
such that every pair of the numbers sum to a perfect square. By the pigeonhole principle, we know that
of the numbers must be on cards in the same pile, and hence, when
, there will always be a pile with
numbers that sum to a perfect square.
~Mathdreams
Solution 2
For the statement to be true, there must be at least three pairs whose sum is each a perfect square. There must be p,q,r such that
and
,
.
WLOG... Equation
![]()
by equation 1
...(1)
...(2)
...(3)
if we add (2) and (3) to (1),
(1) + (2) + (3)
if we assume that x, y, and z is close enough,
At this time , so let's put
to this
where
fits perfectly
therefore the minimum of fits the proposition so the proposition is true
~Mathhyhyhy
~Kingfireboy
Solution 3
Claim: If , then there exist at least three perfect squares between
and
inclusive.
Proof: If , then the perfect squares
,
, and
are between
and
.
What if ? Let
. Note that
Moreover, is increasing because
So . Thus there are at least three distinct integers between
and
, and their squares will lie between
and
. This proves the claim.
Now given any , it follows from the claim that there exist three consecutive squares
,
, and
such that
and therefore
The three numbers ,
, and
have the property that the sum of any two of them is a perfect square:
\begin{align*} (2k^2 - 4k) + (2k^2 + 1) &= (2k - 1)^2, \\ (2k^2 - 4k) + (2k^2 + 4k) &= (2k)^2, \\ (2k^2 + 1) + (2k^2 + 4k) &= (2k + 1)^2. \end{align*}
By the pigeonhole principle, cards showing two of these numbers will end up in the same pile, and the sum of those cards’ numbers will be a perfect square.
See also
2021 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |