Выбираем два числа

[Ktina]

а) Докажите, что из 2018 попарно различных положительных вещественных чисел можно выбрать два таких числа, что ни одно из оставшихся не равно ни сумме, ни разности выбранных чисел.

б) А если чисел 2019?

в) А если числа не обязаны быть положительными?

[Dendr]

а) Пусть A - наибольшее из чисел. Из оставшихся 2017 отбросим все пары чисел, дающие в сумме A (то есть, отбрасываем число N тогда и только тогда, когда в наборе есть N-A, и это второе число отбрасываем тоже). Поскольку мы выбрасываем четное количество чисел, то останется хотя бы одно. Если больше одного - выберем произвольное, назовем его B.

Благодаря указанному отбору, среди исходных чисел нет числа A-B. Но также, поскольку B>0, то A+B>A, а значит, отсутствует наборе. Таким образом, среди 2018 чисел всегда можно найти два таких числа.

б) Пусть A - снова наибольшее из чисел. Если мы повторим действия из пункта "а", и у нас останутся числа, то можно поступить так же, и числа найдены.
Пусть теперь $\forall a_i (i=1..1009) \exists b_i=A-a_i$. Ясно, что пары $a_i, b_i$ не годятся, как и "спаривание" числа A с любым другим. Рассмотрим второе по величине число C и повторим отбор из прошлой задачи. Теперь должно остаться хотя бы одно число. Если это не A-C, то мы нашли подходящую пару. Выясним это.
Для наглядности расположим числа по возрастанию:
$A-C=a_1<a_2<...<a_1_0_0_9<A-a_1_0_0_9<...<A-a_2<C<A$
Чтобы осталось только A-C, все другие должны найти пару, дающую в сумме C. В частности, существует число $C-(A-a_2)=a_2-a_1<a_2$. Но это только $a_1=A-C$. Таким образом, после отбора останется некое число $D\ne A-C$.
По построению в наборе нет числа C-D, а C+D>C, но не равно A. Следовательно, необходимая пара найдена.

Как видно из рассуждений выше, при любом четном размере набора искомой парой может быть наибольшее число набора A, и число B такое, что A-B нет в наборе. При любом нечетном - если B найдено, то пару образуют второе наибольшее C и число D, найденное по тому же принципу.
"Любой четный/нечетный размер" здесь подразумевает "больший 3": набор a, b, a+b не позволяет совершить задуманное.

в) Добавление ноля не меняет рассуждений - просто не используем его, оставляя наборы из 2017 и 2018 чисел соотвественно, а вот с отрицательными числами... Что такое "разность" в этом случае?
Но вроде контрпримеры такие:
-1008, -1007, ..., 1009.
-1009, -1008, ..., 1009.

[Ktina]

Dendr
Круто! Спасибо большое-пребольшое!

[Karan]

Тема перемещена из форума «Загадки, головоломки, ребусы» в форум «Олимпиадные задачи (М)»

[Dendr]

Оставалось чувство недосказанности, поэтому вернулся к задаче - к пункту (в). Не все так просто: контрпример хорош для нечетного $N=2k+1$.
Для любой пары среди чисел $-k, -(k-1), ... -1, 0, 1, ..., k$ возможно два случая:
1) $0<m-n \leqslant k$ - и всегда среди оставшихся будет свободным либо $m-n$, либо $n-m$.
2) $m-n>k$ - то есть $m>0, n<0$, тогда $m+n=m-\left\lvert n\right\rvert$, и это число гарантированно будет среди оставшихся.
(примечание - все примеры даю в целых числах, но всегда можно домножить их на, допустим, 5,379 для рациональных примеров или на корень из 17 для иррациональных)

Для четного $N=2k$ набор $-(k-1), ... k$ уже не подойдет: пара $(0,k)$ дает сумму $k$, а разность $k$ либо $-k$. Среди прочих они не встретятся, и это не контрпример.

Если использовать другой подход и рассмотреть делимость на 3, то для $N=6p$ контрпример находится:
$-2p, ..., -1, 1, ... 4p$.
Действительно, если $0<m-n \leqslant 2p$, всегда будет свободным $m-n$ или $n-m$.
Если $2p<m-n \leqslant 4p$, значит,
либо $n<0, 0<m\leqslant 2p$ - в этом случае $m-n>p$ будет свободным,
либо $n<0, m>2p$ - тогда свободно $0<m+n<m$,
либо $n>0, m>2p, m\ne 2n$ - гарантированно свободно $m-n$,
наконец, $0<2n=m\leqslant 4p$ - тогда свободно $-n$
Таким образом, для любой пары чисел такого набора всегда в оставшейся части набора существует либо их сумма, либо разность.

При $N=6p+4$ для контрпримера подойдет набор $-2p-1, ..., -1, 1, ... 4p+3$, обоснования такие же с точностью до замены пределов интервалов.

А вот при $N=6p+2$ общей схемы (пока) не обнаружилось, но можно составить частный пример при $N=8$: -4, -3, -1, 1, 2, 3, 5, 6. Несложно убедиться, для для любой из 28 пар среди оставшихся 6 чисел встретится либо их сумма, либо разность (с минусом или без).
При $N=14$ возникает столько связей, что вручную подбор затягивается. Хотя интуитивно контрпример должен найтись. Можно на досуге программку накатать.