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"

(→‎Solution)
(→‎Video Solutions)
 
(23 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 \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==
+
== Video Solutions（中文解说）in Chinese but subtitle in English ==
−
sol 1: easy one)
+
https://youtu.be/rnSRjcEfVCU
−
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 p+q = x^2 and q+r = y^2, p+r = z^2.
 
  
−
WLOG n<= p<= q<= r <= 2n ... Equation 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:
 +
<cmath>\usepackage{amsmath}
 +
\begin{align*}
 +
a+b &= p^2 \\
 +
b+c &= q^2 \\
 +
a+c &= r^2
 +
\end{align*}</cmath>
 +
where <math>a</math>, <math>b</math>, and <math>c</math> are numbers on three of the cards. Solving for <math>a</math>, <math>b</math>, and <math>c</math> in terms of <math>p</math>, <math>q</math>, and <math>r</math> tells us that <math>a = \frac{p^2 + r^2 - q^2}{2}</math>, <math>b=\frac{p^2 + q^2 - r^2}{2}</math>, and <math>c=\frac{q^2 + r^2 - p^2}{2}</math>. We can then substitute <math>p^2 = (2e-1)^2</math>, <math>q^2 = (2e)^2</math>, and <math>r^2 = (2e+1)^2</math> to cancel out the <math>2</math>s in the denominatior, and simplifying gives <math>a = 2e^2 + 1</math>, <math>b = 2e(e-2)</math>, and <math>c = 2e(e+2)</math>. Now, we have to prove that there exists three numbers in these forms between <math>n</math> and <math>2n</math> when <math>n \ge 100</math>. Notice that <math>b</math> will always be the least of the three and <math>c</math> will always be the greatest of the three. So it is sufficient to prove that there exists numbers in the form <math>2e(e-2)</math> and <math>2e(e+2)</math> between <math>n</math> and <math>2n</math>.
 +
 
 +
 
 +
For two numbers in the form of <math>2e(e-2)</math> and <math>2e(e+2)</math> to be between <math>n</math> and <math>2n</math>, the inequalities
 +
<cmath>\usepackage{amsmath}
 +
\begin{align*}
 +
2e(e-2) &\ge n \\
 +
2e(e+2) &\le 2n \\
 +
\end{align*}</cmath>
 +
must be satisfied. We can then expand and simplify to get that
 +
<cmath>\usepackage{amsmath}
 +
\begin{align*}
 +
e^2 - 2e - \frac{n}{2} &\ge 0 \\
 +
e^2 + 2e - n &\le 0. \\
 +
\end{align*}</cmath>
 +
Then, we can complete the square on the left sides of both inequalities and isolate <math>e</math> to get that
 +
<cmath>\usepackage{amsmath}
 +
\begin{align*}
 +
e &\ge \sqrt{1 + \frac{n}{2}} + 1 \\
 +
e &\le \sqrt{1 + n} - 1 \\
 +
\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</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
  
−
p = (x^2 + z^2 – y^2) / 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
  
−
q = (x^2 + y^2 – z^2) / 2
+
<math>p+q = x^2</math> and <math>q+r = y^2</math>, <math>p+r = z^2</math>.
  
−
r = (y^2 + z^2 – x^2) / 2
+
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>
 +
<math>r = \frac{(y^2 + z^2 – x^2)}{2}</math>
  
 
by equation 1
 
by equation 1
  
−
2n <= x^2 + z^2 – y^2 <= 4n
+
<math>2n \le x^2 + z^2 – y^2 \le 4n</math>  ...(1)
 +
<math>2n \le x^2 + y^2 – z^2 \le 4n</math>  ...(2)
 +
<math>2n \le y^2 + z^2 – z^2 \le 4n</math>  ...(3)
  
−
2n <= x^2 + y^2 – z^2 <= 4n
+
if we add (2) and (3) to (1),
  
−
2n <= y^2 + z^2 – z^2 <= 4n
+
(1) + (2) + (3) <math>\Rightarrow</math>
  
 +
<math>6n \le x^2 + y^2 + z^2 \le 12n</math>
  
−
6n <= x^2 + y^2 + z^2 <= 12n
+
if we assume that x, y, and z is close enough,
  
−
6n <= 3x^2 <= 12n
+
<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
−
2n <= x^2 <= 4n
 
  
−
√(2n) <= x <= 2√n
+
<math>10\sqrt{2} \le (x,y,z) \le 20</math>
 +
<math>15 \le (x,y,z) \le 20</math>
  
−
At this time n >= 100, so
+
where
  
−
10 * √2 <= x,y,z <= 20
+
<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>
  
−
15 <= x,y,z <= 20
+
<math>x = 16, y = 18, z = 20</math> fits perfectly
  
−
where
+
therefore the minimum of <math>n</math> fits the proposition so the proposition is true
  
−
2|x^2 + y^2 – z^2
+
~Mathhyhyhy
  
−
2|x^2 + z^2 – y^2
+
~Kingfireboy
  
−
2|y^2 + z^2 – z^2
+
== Solution 3 ==
  
−
x = 16, y = 18, z = 20 fits perfectly
+
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.
−
therefore for the minimum of n fits the proposition so the proposition is true
 
  
−
~Mathhyhyhy
+
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
  
−
sol 2)
+
<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:
  
−
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}
 
 
\begin{align*}
 
\begin{align*}
−
a+b &= p^2 \\
+
(2k^2 - 4k) + (2k^2 + 1) &= (2k - 1)^2, \\
−
b+c &= q^2 \\
+
(2k^2 - 4k) + (2k^2 + 4k) &= (2k)^2, \\
−
a+c &= r^2
+
(2k^2 + 1) + (2k^2 + 4k) &= (2k + 1)^2.
−
\end{align*}</cmath>
+
\end{align*}
−
where <math>a</math>, <math>b</math>, and <math>c</math> are numbers on three of the cards. Solving for <math>a</math>, <math>b</math>, and <math>c</math> in terms of <math>p</math>, <math>q</math>, and <math>r</math> tells us that <math>a = \frac{p^2 + r^2 - q^2}{2}</math>, <math>b=\frac{p^2 + q^2 - r^2}{2}</math>, and <math>c=\frac{q^2 + r^2 - p^2}{2}</math>. We can then substitute <math>p^2 = (2e-1)^2</math>, <math>q^2 = (2e)^2</math>, and <math>r^2 = (2e+1)^2</math> to cancel out the <math>2</math>s in the denominatior, and simplifying gives <math>a = 2e^2 + 1</math>, <math>b = 2e(e-2)</math>, and <math>c = 2e(e+2)</math>. Now, we have to prove that there exists three numbers in these forms between <math>n</math> and <math>2n</math> when <math>n \ge 100</math>. Notice that <math>b</math> will always be the least of the three and <math>c</math> will always be the greatest of the three. So it is sufficient to prove that there exists numbers in the form <math>2e(e-2)</math> and <math>2e(e+2)</math> between <math>n</math> and <math>2n</math>.
 
  
 +
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.
  
−
For two numbers in the form of <math>2e(e-2)</math> and <math>2e(e+2)</math> to be between <math>n</math> and <math>2n</math>, the inequalities
+
== See also ==
−
<cmath>\usepackage{amsmath}
+
{{IMO box|year=2021|before=First Problem|num-a=2}}
−
\begin{align*}
 
−
2e(e-2) &\ge n \\
 
−
2e(e+2) &\le 2n \\
 
−
\end{align*}</cmath>
 
−
must be satisfied. We can then expand and simplify to get that
 
−
<cmath>\usepackage{amsmath}
 
−
\begin{align*}
 
−
e^2 - 2e - \frac{n}{2} &\ge 0 \\
 
−
e^2 + 2e - n &\le 0. \\
 
−
\end{align*}</cmath>
 
−
Then, we can complete the square on the left sides of both inequalities and isolate <math>e</math> to get that
 
−
<cmath>\usepackage{amsmath}
 
−
\begin{align*}
 
−
e &\ge \sqrt{1 + \frac{n}{2}} + 1 \\
 
−
e &\le \sqrt{1 + n} - 1 \\
 
−
\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</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
+
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 23:19, 13 November 2024

Problem

Let $n \geq 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.

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]

Video Solutions（中文解说）in Chinese but subtitle in English

https://youtu.be/rnSRjcEfVCU

Solution 1

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

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

$p+q = x^2$ and $q+r = y^2$, $p+r = z^2$. 

WLOG $n \le p \le q \le r \le 2n$ ...  Equation $1$

$p = \frac{(x^2 + z^2 – y^2)}{2}$
$q = \frac{(x^2 + y^2 – z^2)}{2}$
$r = \frac{(y^2 + z^2 – x^2)}{2}$

by equation 1 

$2n \le x^2 + z^2 – y^2 \le 4n$   ...(1)
$2n \le x^2 + y^2 – z^2 \le 4n$   ...(2)
$2n \le y^2 + z^2 – z^2 \le 4n$   ...(3)

if we add (2) and (3) to (1),

(1) + (2) + (3) $\Rightarrow$ 

$6n \le x^2 + y^2 + z^2 \le 12n$

if we assume that x, y, and z is close enough,

$6n \le 3x^2 \le 12n$
$2n \le x^2 \le 4n$
$\sqrt{(2n)} \le x \le 2\sqrt{n}$

At this time $100 \le n$, so let's put $n = 100$ to this 

$10\sqrt{2} \le (x,y,z) \le 20$
$15 \le (x,y,z) \le 20$

where 

$2|x^2 + y^2 - z^2$ 
$2|x^2 + z^2 - y^2$ 
$2|y^2 + z^2 - z^2$

$x = 16, y = 18, z = 20$ fits perfectly

therefore the minimum of $n$ fits the proposition so the proposition is true

~Mathhyhyhy

~Kingfireboy

Solution 3

Claim: If $n \geq 100$, then there exist at least three perfect squares between $n/2 + 1$ and $n + 1$ inclusive.

Proof: If $100 \leq n \leq 125$, then the perfect squares $64$, $81$, and $100$ are between $n/2 + 1$ and $n + 1$.

What if $n \geq 126$? Let $f(t) = \sqrt{t + 1} - \sqrt{t/2 + 1}$. Note that

\[f(126) = \sqrt{127} - \sqrt{64} > 11 - 8 = 3.\]

Moreover, $f$ is increasing because

\[f'(t) = \frac{1}{\sqrt{4t + 4}} - \frac{1}{\sqrt{8t + 16}} > 0.\]

So $f(n) \geq f(126) > 3$. Thus there are at least three distinct integers between $\sqrt{n/2 + 1}$ and $\sqrt{n + 1}$, and their squares will lie between $n/2 + 1$ and $n + 1$. This proves the claim.

Now given any $n \geq 100$, it follows from the claim that there exist three consecutive squares $(k - 1)^2$, $k^2$, and $(k + 1)^2$ such that

\[\frac{n}{2} + 1 \leq (k - 1)^2, k^2, (k + 1)^2 \leq n + 1,\]

and therefore

\[n \leq 2k^2 - 4k, 2k^2 + 1, 2k^2 + 4k \leq 2n.\]

The three numbers $2k^2 - 4k$, $2k^2 + 1$, and $2k^2 + 4k$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_IMO_Problems/Problem_1&oldid=233411"