# Difference between revisions of "2021 IMO Problems/Problem 1"

Mathdreams (talk | contribs) (Created page with "==Problem== Let <math>n \geqslant 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<...") |
|||

(4 intermediate revisions by 4 users not shown) | |||

Line 1: | Line 1: | ||

==Problem== | ==Problem== | ||

Let <math>n \geqslant 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. | Let <math>n \geqslant 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== | ||

+ | https://youtu.be/cI9p-Z4-Sc8 [Video contains solutions to all day 1 problems] | ||

+ | |||

+ | https://youtu.be/0Vd4ZBEr3o4 | ||

+ | |||

+ | https://www.youtube.com/watch?v=a3L9O7b1WYg [disclaimer: only a sketch of the solution] | ||

+ | |||

==Solution== | ==Solution== | ||

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: | ||

Line 30: | Line 38: | ||

e &\le \sqrt{1 + n} - 1 \\ | e &\le \sqrt{1 + n} - 1 \\ | ||

\end{align*}</cmath> | \end{align*}</cmath> | ||

− | Notice that <math>e</math> must be an integer, so there must be an integer between <math>\sqrt{1 + n} - 1</math> and <math>\sqrt{1 + \frac{n}{2}} + 1</math>. If <math>\sqrt{1 + n} - 1</math> and <math>\sqrt{1 + \frac{n}{2}} + 1</math> differ by at least <math>1</math>, then we can guarantee that there is an integer between them (and those integers are the possible values of <math>e</math>). Setting up the inequality <math>\sqrt{1 + n} - \sqrt{1 + \frac{n}{2}} - 2 \ge 1</math> and solving for <math>n</math> tells us that <math>n \in [107, \infty)</math> always works. Testing the remaining <math>7</math> numbers (<math>100 | + | Notice that <math>e</math> must be an integer, so there must be an integer between <math>\sqrt{1 + n} - 1</math> and <math>\sqrt{1 + \frac{n}{2}} + 1</math>. If <math>\sqrt{1 + n} - 1</math> and <math>\sqrt{1 + \frac{n}{2}} + 1</math> differ by at least <math>1</math>, then we can guarantee that there is an integer between them (and those integers are the possible values of <math>e</math>). Setting up the inequality <math>\sqrt{1 + n} - \sqrt{1 + \frac{n}{2}} - 2 \ge 1</math> and solving for <math>n</math> tells us that <math>n \in [107, \infty)</math> always works. Testing the remaining <math>7</math> numbers (<math>100</math> to <math>106</math>) manually tells us that there is an integer between <math>\sqrt{1 + n} - 1</math> and <math>\sqrt{1 + \frac{n}{2}} + 1</math> when <math>n \ge 100</math>. Therefore, there exists a triplet of integers <math>(a,b,c)</math> with <math>a, b, c \in \{n, n+1, ..., 2n\}</math> when <math>n \ge 100</math> such that every pair of the numbers sum to a perfect square. By the pigeonhole principle, we know that <math>2</math> of the numbers must be on cards in the same pile, and hence, when <math>n \ge 100</math>, there will always be a pile with <math>2</math> numbers that sum to a perfect square. <math>\square</math> |

~Mathdreams | ~Mathdreams |

## Latest revision as of 10:26, 24 July 2021

## 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

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