IMO 2021, Problem 1

Discussion on International Mathematical Olympiad (IMO)
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
IMO 2021, Problem 1

Unread post by tanmoy » Wed Jul 21, 2021 8:07 pm

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.
"Questions we can't answer are far better than answers we can't question"

User avatar
Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: IMO 2021, Problem 1

Unread post by Anindya Biswas » Thu Jul 22, 2021 6:36 pm

It's sufficient to show that there exists integers $n\leq a,b,c\leq 2n$ such that $a+b=r^2, b+c=p^2, c+a=q^2$.
Solving, we get,
$a=\frac{p^2+q^2+r^2}2-p^2$
The expression for $b,c$ are similar.

Here, $p^2+q^2+r^2$ must be even.
Let's assume $p=2k-1,q=2k,r=2k+1$.
In that case, $2n\geq a>b>c\geq n$.
  • Form $a\leq2n$, we get,
    $6k^2+1-(2k-1)^2\leq2n$
    $\Rightarrow 2k^2+4k\leq2n$
    $\Rightarrow (k+1)^2\leq n+1$
    $\Rightarrow k\leq \sqrt{n+1}-1$
  • From $c\geq n$, we get,
    $6k^2+1-(2k+1)^2\geq n$
    $\Rightarrow 2k^2-4k\geq n$
    $\Rightarrow (k-1)^2\geq \frac{n}2+1$
    $\Rightarrow k\geq \sqrt{\frac{n}2+1}+1$
So, it's sufficient to show that there exist an integer between $\sqrt{\frac{n}2+1}+1$ and $\sqrt{n+1}-1$.

It's easy to verify that when $n\geq107$, $\left(\sqrt{n+1}-1\right)-\left(\sqrt{\frac{n}2+1}+1\right)>1$. So, an integer must exist between them.
When $100\leq n\leq106$, $k=9$ works.
So, whenever $n\geq100$, it must be true.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply