Олимпиада Туймаада по математике. Старшая лига. 2014 год

На столе лежит чётное число карточек, на каждой из которых написано натуральное число. Пусть $a_k$ — количество карточек, на которых написано число $k$. Оказалось, что $$a_n-a_{n-1}+a_{n-2}-\ldots\geq 0 $$ для каждого натурального $n$. Докажите, что карточки можно разложить по парам, в каждой из которых числа отличаются на 1. ( А. Голованов )

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

Пусть на карточке с наименьшим натуральным числом написано число $x$. Тогда подставив под данную формулу $n=x+1$, мы получим:

$a_{x+1}-a_{x} \geq 0 \Rightarrow a_{x+1} \geq a_{x}.$ Отсюда можно утверждать о том, что для каждой карточки с числом $x$ в пару найдется карточка с числом $x+1$.

Далее, подставив под формулу $n=x+2$, можно получить:

$a_{x+2}-a_{x+1}+a_{x} \geq 0 \Rightarrow a_{x+2} \geq a_{x+1}-a_{x}.$ Отсюда же можно утверждать о том, что для всех оставшихся $(a_{x+1}-a_{x})$ карточек с числом $x+1$, которые не вошли в пару с карточками $x$ , в пару найдутся карточки с числом $x+2$.

Делая подобные действия для $n=x+3$, получим:

$a_{x+3}-a_{x+2}+a_{x+1}-a_{x} \geq 0 \Rightarrow a_{x+3} \geq a_{x+2}-a_{x+1}+a_{x}.$ И делаем вывод о том, что для каждой карточки с числом $x+2$, которая не вошла в пару с оставшимися числами $x+1$, в пару точно найдется карточка с числом $x+3$.

Пусть на карточке с наибольшим натуральным числом написано число $y$.

Тогда повторяя предыдущие действия мы можем сказать о том что,

$a_{y}-a_{y-1}+a_{y-2}-a_{y-3}+\ldots \geq 0 \Rightarrow a_{y} \geq a_{y-1}-a_{y-2}+a_{y-3}-\ldots \Rightarrow$ для каждой карточки с числами от $x$ до $y-1$ точно найдутся пары.

Подставив же под данную нам формулу $y+1$ мы получим:

$a_{y+1}-a_{y}+a_{y-1}-a_{y-2}+a_{y-3}-\ldots \geq 0.$ Так как $y$ это наибольшее натуральное число, понятно, что $a_{y+1}=0$, и мы имеем:

$-a_{y} \geq -a_{y-1}+a_{y-2}-a_{y-3}+\ldots \Rightarrow a_{y} \leq a_{y-1}-a_{y-2}+a_{y-3}-\ldots $

Раньше мы уже получали $a_{y} \geq a_{y-1}-a_{y-2}+a_{y-3}-\ldots$

Поэтому, получаем равенство: $a_{y} = a_{y-1}-a_{y-2}+a_{y-3}-\ldots$ , то есть количество оставшихся карточек с числом $y-1$ равна $a_{y}$, и для всех карточек с числом $y$ парой будут числа $y-1$.

Таким образом, все числа $x$ могут быть в паре с числами $x+1$, числа $x+1$, которые не вошли в пару c $x$ могут войти в пару с числами $x+2$ $\ldots$ числа $y-1$, которые не вошли в пару с $y-2$ могут войти в пару с числами $y$

и количество оставшихся чисел $y-1$ равна количеству карточек с числом $y$, что позволяет им всем быть в паре.