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

[qwert129]

Среди натуральных чисел от 1 до 365 выбрали 29 чисел. Докажите, что среди них найдутся 4 числа, таких , что $a+b=c+d$

[Null]

Разности повторятся. Случаи $a-b=b-c$ мешаются, но повторений разностей довольно много.

[Rak so dna]

qwert129 в сообщении #1623247 писал(а):

Среди натуральных чисел от 1 до 365 выбрали 29 чисел. Докажите, что среди них найдутся 4 числа, таких , что $a+b=c+d$

Постройте последовательность с минимальными неотрицательными неповторяющимися разностями между соседними числами и оцените $29$-й её член.

[Null]

$b+b=a+c$ это "найденные 4 числа"?
Иначе

Rak so dna в сообщении #1623263 писал(а):

неповторяющимися разностями между соседними числами

не работает.

[Rak so dna]

Null согласен. Правильная "минимальная" последовательность хитрее. Если опять не ошибся, то выглядит она так: $1,1,1,2,3,5,8,13,21,34...$

(Оффтоп)

Только сейчас увидел, что это Фибоначчи

$(1,1),(1,2),(3,5),(8,13),(21,34),$

Очередная пара строится так: разность с $34$ должна быть больше $21-1=20,$ поэтому первое число пары $34+21=55$ Разность между числами в паре должна быть больше $34-1=33$ второе число пары $55+34=89$

Ну и поскольку $15$-е число последовательности $377$, то даже $15$ чисел достаточно. Или нет?

[worm2]

Я думаю, подразумевалось что-то такое:

Если среди чисел найдутся две пары совпадающих ($a_i=a_j$, $a_k=a_m$, и все индексы $i$, $j$, $k$, $m$ различны), то задача решена: $a_i+a_k=a_j+a_m$.

Иначе среди чисел повторяться может только одно число, максимум трижды. Пусть оно так и есть, без ограничения общности $a_1=a_2=a_3$, все остальные числа различны. Идём от противного, пусть для любых попарно различных индексов $i$, $j$, $k$, $m$ суммы не совпадают: $a_i+a_k \ne a_j+a_m$. Подсчитаем, сколько всего таких сумм $a_i+a_j$ для всевозможных различных $i$ и $j$, $j>i$. Их $29\cdot 28=812$. Среди них есть совпадающие с совпадающими индексами: $a_1+a_i=a_2+a_i=a_3+a_i$, где $i>3$, плюс ещё три комбинации $a_1+a_2=a_1+a_3=a_2+a_3$. Таких комбинаций $26\cdot 3+3=81$ штука, они дают $26+1=27$ различных значений. Исключим эту 81 комбинацию. Остальные комбинации $i$ и $j$ дают $812-81=731$ значение, причём если среди них есть совпадающие индексы, например, ($i$, $j$) и ($j$, $k$), то суммы обязательно разные ($a_i=a_k$ уже не может быть, мы все такие случаи исключили), а если все индексы попарно различны, то суммы различны по предположению "от противного". Значит, у нас $27+731=758$ различных сумм. Но два натуральных числа, не превышающих $365$, в сумме могут дать значение от $2$ до $365\cdot 2=730$, всего $729$ различных значений. Противоречие.

Случаи, когда одно число повторяется лишь дважды, и случай, когда все числа различны, рассматриваются отдельно (они ещё проще).

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

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

[venco]

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

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

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

[Null]

worm2 в сообщении #1623334 писал(а):

всевозможных различных $i$ и $j$, $j>i$. Их $29\cdot 28=812$.

У меня в 2 раза меньше выходит.

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

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

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

Вроде условие - неповторяющиеся?

[Null]

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

Вроде условие - неповторяющиеся?

$a-b=b-c\Rightarrow b+b=a+c$ - разности одинаковые, но 4 числа не получаются.

[Yadryara]

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

Вроде условие - неповторяющиеся?

Что "неповторяющиеся" ? Вот условие:

qwert129 в сообщении #1623247 писал(а):

Среди натуральных чисел от 1 до 365 выбрали 29 чисел. Докажите, что среди них найдутся 4 числа, таких , что $a+b=c+d$

"29 чисел", "4 числа". Не сказано ни "попарно различных", ни даже просто "различных".

[Null]

Yadryara в сообщении #1623409 писал(а):

"29 чисел", "4 числа". Не сказано ни "попарно различных", ни даже просто "различных".

Формально вопрос к qwert129, но какие то ограничения точно есть иначе $a+b=a+b$ всегда подходит.

[ihq.pl]

Yadryara в сообщении #1623409 писал(а):

Не сказано ни "попарно различных", ни даже просто "различных".

Ну, это как-то просто. Максимальное число отрезков разной длины равно 364. Если число отрезков больше, среди них найдутся как минимум два отрезка равной длины.

-- 22.12.2023, 15:47 --

Да и почему именно 29? Могли бы тогда взять и 28.

-- 22.12.2023, 16:01 --

Пардон, не могли бы:) Похоже, действительно нет никаких ограничений.

[qwert129]

Да, все числа различны.