2014 dxdy logo

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

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




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

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение21.12.2023, 08:06 
Разности повторятся. Случаи $a-b=b-c$ мешаются, но повторений разностей довольно много.

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение21.12.2023, 09:30 
Аватара пользователя
qwert129 в сообщении #1623247 писал(а):
Среди натуральных чисел от 1 до 365 выбрали 29 чисел. Докажите, что среди них найдутся 4 числа, таких , что $a+b=c+d$
Постройте последовательность с минимальными неотрицательными неповторяющимися разностями между соседними числами и оцените $29$-й её член.

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение21.12.2023, 09:40 
$b+b=a+c$ это "найденные 4 числа"?
Иначе
Rak so dna в сообщении #1623263 писал(а):
неповторяющимися разностями между соседними числами
не работает.

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение21.12.2023, 10:38 
Аватара пользователя
Null согласен. Правильная "минимальная" последовательность хитрее. Если опять не ошибся, то выглядит она так: $1,1,1,2,3,5,8,13,21,34...$

(Оффтоп)

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


$(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$ чисел достаточно. Или нет?

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение21.12.2023, 17:48 
Аватара пользователя
Я думаю, подразумевалось что-то такое:

Если среди чисел найдутся две пары совпадающих ($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$ различных значений. Противоречие.

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

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

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение21.12.2023, 20:21 
Евгений Машеров в сообщении #1623341 писал(а):
Очевидно, минимальную сумму среди неповторяющихся чисел будут иметь 1, 2, 3... 28.
Две разности могут совпадать, если они используют одно и то же число.

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение21.12.2023, 21:22 
worm2 в сообщении #1623334 писал(а):
всевозможных различных $i$ и $j$, $j>i$. Их $29\cdot 28=812$.
У меня в 2 раза меньше выходит.

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение22.12.2023, 11:13 
Аватара пользователя
venco в сообщении #1623357 писал(а):
Две разности могут совпадать, если они используют одно и то же число.


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

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение22.12.2023, 11:19 
Евгений Машеров в сообщении #1623404 писал(а):
Вроде условие - неповторяющиеся?

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

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение22.12.2023, 12:04 
Аватара пользователя
Евгений Машеров в сообщении #1623404 писал(а):
Вроде условие - неповторяющиеся?

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

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

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

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение22.12.2023, 12:12 
Yadryara в сообщении #1623409 писал(а):
"29 чисел", "4 числа". Не сказано ни "попарно различных", ни даже просто "различных".
Формально вопрос к qwert129, но какие то ограничения точно есть иначе $a+b=a+b$ всегда подходит.

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение22.12.2023, 14:11 
Yadryara в сообщении #1623409 писал(а):
Не сказано ни "попарно различных", ни даже просто "различных".

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

-- 22.12.2023, 15:47 --

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

-- 22.12.2023, 16:01 --

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

 
 
 
 Re: Найдутся числа a+b=c+d из 29 чисел
Сообщение22.12.2023, 16:14 
Да, все числа различны.

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group