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

Revision as of 05:18, 31 May 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]

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  ...  Equation

by equation 1

   ...(1)
   ...(2)
   ...(3)

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

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

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

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

where

$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$ .

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 if $n \geq 126$ , then $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.

2021 IMO (Problems) • Resources
Preceded by First Problem	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

Page

Toolbox

Search