2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Выбираем два числа
Сообщение07.05.2018, 23:26 
Аватара пользователя


01/12/11

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

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

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

 Профиль  
                  
 
 Re: Выбираем два числа
Сообщение08.05.2018, 14:59 


02/04/18
240
а) Пусть 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.

 Профиль  
                  
 
 Re: Выбираем два числа
Сообщение08.05.2018, 15:12 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Posted automatically
Сообщение10.05.2018, 10:39 
Модератор


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

 Профиль  
                  
 
 Re: Выбираем два числа
Сообщение11.05.2018, 12:03 


02/04/18
240
Оставалось чувство недосказанности, поэтому вернулся к задаче - к пункту (в). Не все так просто: контрпример хорош для нечетного $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$ возникает столько связей, что вручную подбор затягивается. Хотя интуитивно контрпример должен найтись. Можно на досуге программку накатать.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group