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

Дано целое число $n > 100$. Целые числа от 1 до $4n$ разбиты на $n$ групп, по 4 числа в каждой. Докажите, что найдутся не менее $\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$. Доказано