Найдутся числа a+b=c+d из 29 чисел

[bot]

Сибирская математическая олимпиада 2019
2-4 курсы (для вузов с профилирующей математикой (МП)) Пятая задача

[Razgulyay]

Обозначим упорядоченный по возрастанию набор из чисел $a_i,\ i=1,2,..,29$. Без потери общности, запишем условие в виде $a_i - a_j = a_k - a_l$, $i>j,\ k>l$, $i,j,k,l$ попарно различны. Всего в наборе $29\cdot14=406$ упорядоченных по возрастанию пар. Некоторые из них могут иметь идентичные разности в случае $a_i - a_j = a_j - a_k$, но для каждого $a_j$ может быть только один такой случай:
Пусть $a_i - a_j = a_j - a_k = \delta_1$ и $a_m - a_j = a_j - a_n = \delta_2$, тогда $a_m - a_i = a_k - a_n = \delta_2 - \delta_1$ и условие выполнено.
Тогда имеем, что набор, если условие не выполнено, должен иметь $406 - (29-4) = 381$ различных по значению пар разностей. Значит, минимальное возможное $a_{29}=382>365$. ч.т.д.

[venco]

Чёрт! Когда засыпал, придумал точно такое доказательство, но запостить первым не успел. :)

[Евгений Машеров]

Евгений Машеров в сообщении #1623341 писал(а):

Мне как-то совсем просто представляется. Предположим, что выбраны числа, для которых равенство не выполняется для любого выбора 4 из них. Можно считать без потери общности, что $a>b$. $c>d$ и перенести b, d в другую часть.То есть нет двух пар чисел с одинаковыми разностями. Упорядочим выбранные числа по возрастанию и выпишем 28 их разностей. Максимальное число равно сумме всех разностей плюс минимальное. Очевидно, минимальную сумму среди неповторяющихся чисел будут иметь 1, 2, 3... 28. Все остальные наборы будут иметь сумму больше. А минимальное минимальное число - единица. Тогда максимальное число будет не менее 407. Однако мы выбирали из чисел, не превышающих 365.

[venco]

venco в сообщении #1623357 писал(а):

Евгений Машеров в сообщении #1623341 писал(а):

Очевидно, минимальную сумму среди неповторяющихся чисел будут иметь 1, 2, 3... 28.

Две разности могут совпадать, если они используют одно и то же число.

[bot]

Евгений Машеров в сообщении #1623341 писал(а):

Очевидно, минимальную сумму среди неповторяющихся чисел будут иметь 1, 2, 3... 28.

Как уже указано, не катит. Но рациональное зерно здесь есть - надо рассмотреть сумму малоповторяющихся.
Пусть

$$1\leqslant a_1 < a_2 < \ldots < a_n\leqslant N$$

Рассмотрим сумму всех разностей

$$S=\sum\imits_{1\leqslant i<j\leqslant n}a_j-a_i=(n-1)(a_n-a_1)+(n-2)(a_{n-1}-a_1)+\ldots +(n-1)(a_n-a_1)+2(a_3-a_1)+(a_2-a_1)$$

Верхняя оценка:

$$S\leqslant (n-1)(N-1)+(n-2)(N-2)+\ldots+2(N-n+2)+(N-n+1)\leqslant$$

$$\leqslant N(1+2+\ldots (n-1))-(1\cdot(n-1)+2\cdot(n-2)+\ldots + (n-2)\cdot 2+ (n-1)\cdot 1)=$$

$$=N\cdot\frac{n(n-1)}{2}-\frac{n(n+1)(n+2)}{6}$$

Если среди разностей есть три одинаковых, то необходимая четвёрка есть. Пусть каждая разница повторяется не более двух раз. Тогда имеем нижнюю оценку:

$$S\geqslant 2\left(1+2+\ldots + \frac{n(n-1)}{2}\right), \, \text{если } n\equiv 0,1\pmod 4$$

$$S\geqslant 2\left(1+2+\ldots + \frac{n(n-1)}{2}-1\right) + \frac{n(n-1)}{2}, \, \text{если } n\equiv 2,3\pmod 4$$

Для $N=365$ оценки противоречивы при $n\geqslant 28$.

[bot]

Сбрендил однако. Всего разниц $\binom{n}{2}$, а в нижней оценке их вдвое больше.