Международная олимпиада 2021, Санкт-Петербург, Россия, 2021 год

Дано целое число n > 100. Ваня написал числа $n$, $n+1$, $\ldots,$ $2n$ на $n+1$ карточке, каждое по одному разу. Затем он перемешал колоду из этих карточек и разделил её на две стопки. Докажите, что хотя бы одна из двух стопок содержит две карточки, сумма чисел на которых — точный квадрат.

Комментарий/решение

Попробуем доқазать что среди них есть 3 различные числа $a$, $b$ и $c$ такие что :

$$a+b=l^2$$

$$a+c=m^2$$

$$b+c=k^2$$

Заметим что тогда:

$$2(a+b+c)=l^2+m^2+k^2$$

$$a+b+c=\dfrac{l^2+k^2+m^2}{2}$$

$$a=\dfrac{l^2-k^2+m^2}{2}$$

$$b=\dfrac{l^2+k^2-m^2}{2}$$

$$c=\dfrac{k^2+m^2-l^2}{2}$$

Заметим что $2\mid a+b+c$

Обозначим числа

$l^2$, $k^2$ и $m^2$ как $(2r+x)^2$

$(2r+y)^2$

И $(2r+z)^2$ соответственно

Б.О.О. возьмем что $x>y>z$

Значит $a=2r^2+x+y-z$, $b=2r^2+x-y+z$, $c=2r^2-x+y+z$

Докажем что среди $n $ и $ 2n$ найдутся числа $a$ и $c$ поскольку это минимальное и максимальное среди чисел

Ну и после очевидного неравенства выходит что:

$\sqrt{1+\dfrac{n}{2}}+1 \leq r$

$\sqrt{1+n}-1 \geq r$

Значит $n$ работает для всех чисел $\geq 107$

Проверяем остальные числа от 100 до 106

Пример от 100 до 106:

$a=198$

$b=163$

$c=126$

Докажем что существуют такие $a,b,c$ что $a+b=x^2, b+c=y^2, a+c=z^2$ и $n \leq a,b,c \leq 2n$.

Возьмем $k^2 \leq n < (k+1)^2$.

Тогда след. числа подходят:

$x=2k^2-2$

$y=2k^2-4k+3$

$z=2k^2-8k+6$

Так как $x,y,z <2k^2 \leq 2n$. Остается нам показать что $n \leq x,y,z$. То есть покажем что $x,y,z \geq (k+1)^2 <=> (!) k^2 \geq 2k+3, 6k-2, 10k-5$ что легко доказать индукцией используя то что $k \geq 10$.

возьмем карточки как вершины графа, а ребро проводим если сумма чисел на двух карточках равна квадрату. Если граф двудольный то условие не выполняется, следовательно докажем что в графе есть нечетный цикл. Допустим $x+y=t^2, x+z=(t+1)^2, y+z=(t+2)^2 \Rightarrow x=\frac{t^2-2t-3}{2}, y=\frac{t^2+2t+3}{2}, z=\frac{t^2+6t+5}{2}$ мы знаем по условию что $$x\geq n \Rightarrow t\geq 1+\sqrt{2n+4}$$, $$z\leq 2n \Rightarrow t\leq 2\sqrt{n+1}-3$$ следовательно $t \in [1+\sqrt{2n+4}, 2\sqrt{n+1}-3]$ если этот диапазон $>1$ то тогда найдется подходящее целое число для значения $t$. Несложно заметить , что $F(n)=(2\sqrt{n+1}-3)-(1+\sqrt{2n+4})$ растет вместе с ростом $n$. $n>100 \Rightarrow F(n)>F(100)=2 \sqrt{101}-3-1-\sqrt{204}≈1,8 > 1 \Rightarrow F(n)>1$ то есть в диапазоне найдется целое значение для $t$, то есть в графе найдется нечетный цикл и он не может быть двудольным $$ч.т.д$$