Республиканская олимпиада по математике, 2023 год, 10 класс

Бүтін $n > 100$ саны берілген. 1-ден $4n$-ге дейінгі бүтін сандар төрт саннан тұратын $n$ топқа бөлінген. Осы топтарда келесі шарттарды қанағаттандыратын кем дегенде $\dfrac{(n-6)^2}{2}$ $(a, b, c, d)$ бүтін төрттіктері табылатынын дәлелдеңіз:
   (i) $1\le a < b < c < d\le 4n$;
   (ii) $a, b, c, d$ сандарының кез келген екеуі әртүрлі топта жатыр;
   (iii) $c - b\le |ad - bc|\le d - a$. ( Сатылханов К. )

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

Заметим, что достаточно найти такую четверку $(a,b,c,d)=(a,a+1,c,c+1)$, чтобы все они лежали в разных группах, не совпадали, причем порядок, по которому мы берем $a$ и $с$, не важен.

Возьмем произвольную группу, не включающую элемент $4n$. Возьмем оттуда максимальный элемент, назовем его $a$. Тогда $a+1$ находится в другой группе, причем он существует, выберем его. Теперь надо выбрать $c$, так что $c$ не входит в группы, в которых есть $a, a+1$ и $4n$. Всего остается $n-3$ группы минимум (если $a+1 \ne 4n$, иначе $n-2$). Возьмем $c$ оттуда как максимальный элемент этой группы, тогда для каждого такого $c$ максимум у $7$ из них $c+1$ будет в группе, в которой есть $a$ или $a+1$, ведь всего в объединении групп с $a$ и $(a+1)$ $8$ элементов, но $c+1 \ne a+1$, так как $c \ne a$. Тогда существует хотя бы $(n-3)-7=n-10$ подходящих нам $c$, у которого $c+1$ не в плохих группах. Изначально a можно выбрать $n-1$ способом, тогда всего у нас

$$(n-1)(n-10)$$ пар, но пару $a, a+1, c, c+1$ мы считаем дважды (для $a$ и для $c$), значит пар на самом деле хотя бы $(n-1)(n-10)/2$, что $>(n-6)^2/2$ для $n>100$. Доказано