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 "2021 IMO Problems/Problem 1"

(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<...")
 
m (→‎Solution)
Line 30: Line 30:
 
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 - 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>
+
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

Revision as of 10:10, 21 July 2021

Problem

Let $n \geqslant 100$ be an integer. Ivan writes the numbers $n, n+1, \ldots, 2 n$ each on different cards. He then shuffles these $n+1$ 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.

Solution

If we can guarantee that there exist $3$ cards such that every pair of them sum to a perfect square, then we can guarantee that one of the piles contains $2$ cards that sum to a perfect square. Assume the perfect squares $p^2$, $q^2$, and $r^2$ satisfy the following system of equations: \usepackage{amsmath} \begin{align*} a+b &= p^2 \\ b+c &= q^2 \\ a+c &= r^2 \end{align*} where $a$, $b$, and $c$ are numbers on three of the cards. Solving for $a$, $b$, and $c$ in terms of $p$, $q$, and $r$ tells us that $a = \frac{p^2 + r^2 - q^2}{2}$, $b=\frac{p^2 + q^2 - r^2}{2}$, and $c=\frac{q^2 + r^2 - p^2}{2}$. We can then substitute $p^2 = (2e-1)^2$, $q^2 = (2e)^2$, and $r^2 = (2e+1)^2$ to cancel out the $2$s in the denominatior, and simplifying gives $a = 2e^2 + 1$, $b = 2e(e-2)$, and $c = 2e(e+2)$. Now, we have to prove that there exists three numbers in these forms between $n$ and $2n$ when $n \ge 100$. Notice that $b$ will always be the least of the three and $c$ will always be the greatest of the three. So it is sufficient to prove that there exists numbers in the form $2e(e-2)$ and $2e(e+2)$ between $n$ and $2n$.


For two numbers in the form of $2e(e-2)$ and $2e(e+2)$ to be between $n$ and $2n$, the inequalities \usepackage{amsmath} \begin{align*} 2e(e-2) &\ge n \\ 2e(e+2) &\le 2n \\ \end{align*} must be satisfied. We can then expand and simplify to get that \usepackage{amsmath} \begin{align*} e^2 - 2e - \frac{n}{2} &\ge 0 \\ e^2 + 2e - n &\le 0. \\ \end{align*} Then, we can complete the square on the left sides of both inequalities and isolate $e$ to get that \usepackage{amsmath} \begin{align*} e &\ge \sqrt{1 + \frac{n}{2}} + 1 \\ e &\le \sqrt{1 + n} - 1 \\ \end{align*} Notice that $e$ must be an integer, so there must be an integer between $\sqrt{1 + n} - 1$ and $\sqrt{1 + \frac{n}{2}} + 1$. If $\sqrt{1 + n} - 1$ and $\sqrt{1 + \frac{n}{2}} + 1$ differ by at least $1$, then we can guarantee that there is an integer between them (and those integers are the possible values of $e$). Setting up the inequality $\sqrt{1 + n} - \sqrt{1 + \frac{n}{2}} - 2 \ge 1$ and solving for $n$ tells us that $n \in [107, \infty)$ always works. Testing the remaining $7$ numbers ($100$ to $106$) manually tells us that there is an integer between $\sqrt{1 + n} - 1$ and $\sqrt{1 + \frac{n}{2}} + 1$ when $n \ge 100$. Therefore, there exists a triplet of integers $(a,b,c)$ with $a, b, c \in \{n, n+1, ..., 2n\}$ when $n \ge 100$ such that every pair of the numbers sum to a perfect square. By the pigeonhole principle, we know that $2$ of the numbers must be on cards in the same pile, and hence, when $n \ge 100$, there will always be a pile with $2$ numbers that sum to a perfect square. $\square$

~Mathdreams

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_IMO_Problems/Problem_1&oldid=158820"