IMO 2021, Problem 1
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"
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: IMO 2021, Problem 1
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$.
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.
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$
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
— John von Neumann
Re: IMO 2021, Problem 1
I am very surprised with the way you solved the problem. It's very unique and cool. Suika game