Перед вами в ряд выставлено 30 коробок. У вас в наличии есть 48 шариков. Все имеющиеся шарики нужно разложить по коробкам. Их число в коробке может быть произвольным, но в каждой должен оказаться хотя бы один шарик. Докажите, что в итоге найдётся последовательность стоящих друг за другом коробок, суммарное число шариков в которых будет равным 11.
update
Первый - Илья.Ответ
Запишем на каждой коробке суммарное число шариков в ней и во всех предыдущих. Получим 30 чисел из диапазона от 1 до 48. Далее на каждой коробке запишем ещё по одному числу, которое равно сумме уже написанного и числа 11. Получим ещё 30 чисел, максимальное из которых 48+11=59. Таким образом, мы получили 60 чисел из диапазона от 1 до 59. То есть два каких-то числа будут равны между собой. А равенство двух чисел означает, что в соответствующей последовательности коробок лежит ровно 11 шариков.
Очень интересная задача. Особенно если у нее есть красивое решение :)
ОтветитьУдалитьПока не нашел, пусть по которому иду как-то слишком трудоемким оказался.
Решение довольно интересное. И несложное для понимания, но ведь нужно для него догадаться...
УдалитьМне подсказали красивое решение. Не знаю, стоит ли выкладывать... :)
ОтветитьУдалитьСам бы до такого почти наверняка не додумался :)
Задача вроде бы интересна публике, пускай ещё погадают :)
Удалитькладем по одному шарику. У нас 19 "11цаток" и остается 18 шариков. С каждым новым шариком становится на одну "11цатку" меньше. Значит одна останется
ОтветитьУдалитьа что такое 11цтка в данном случае ?
Удалитьпросто добавляя шарики в 11-ю и в 22-ю коробку вы портите все свои 11цтки
УдалитьДавайте попробуем так:
ОтветитьУдалитьтак как в каждой коробке должен быть хотя б один шарик, то у нас остается 48-30=18 шариков, которые определяют нашу комбинацию расположения шариков по коробкам. Но т.к. коробок 30, а таких вот шариков всего 18, то у нас остается 30-18=12 коробок которые так и останутся с одним шариком.
дальше додумаю завтра, что-то не приходит решение в голову :)
Я шел примерно таким путем, но это получается трудоемко.
УдалитьЕще можно сообразить, что может быть не больше одной коробки, в которой больше 11 шариков, и если такая есть, то среди остальных получается еще больше (22 кажется) таких, в которых по одному.
Это можно развивать дальше, но много вариантов :)
Кстати, если я не путаю, при тех же условиях обязательно найдется последовательность коробок с суммарным количеством шариков 12.
ОтветитьУдалитьА также 13, 14 и 15. То же верно для любых меньших значений.
УдалитьЕсли я не путаю, опять же.
Вот как раз в меньшую сторону получается, а для 12 и больше можно доказать обратное.
УдалитьКонтрпример есть?
УдалитьУ меня вроде корректное доказательство получилось. Но пойду проверю.
так покажи нам доказательство, мы быстро проверим )
УдалитьНу раз просите :)
УдалитьСкажем, для 15 покажу.
Итак, есть 30 чисел х1,...,х30, все целые неотрицательные, в сумме дают 48.
Рассмотрим последовательность частичных сумм:
S0=0
S1=x1
S2=x1+x2
...
S30=x1+...+x30=48.
Заметим, что сумма любой подпоследовательности идущих подряд чисел представляется как разность двух подходящих частичных сумм. Осталось доказать, что найдутся две частичных суммы с разностью 15.
Разобъем все частичные суммы на классы с одинаковым остатком от деления на 15. В каждом таком классе - 3 или 4 числа в интервале от 0 до 48. Для того, чтобы разность любых двух была не равна 15, надо чтобы в каждом классе не нашлось соседних (отличающихся на 15) сумм. Значит, в каждом классе не более двух сумм.
Но всего классов 15, в каждом по два числа - итого 30. А у нас 31. Стало быть, разность каких-то из наших частичных сумм даст ровно 15.
Ч.Т.Д.
Это же доказательство подходит и для меньших значений (14, 13... Для 11 тоже подходит).
Вот для 16 есть очевидный контрпример, конечно :)
Похоже на правду.
УдалитьМоё доказательство не настолько общее. По нему 12 уже проходит. Хотя конкретных примеров с помощью него составить нельзя.
Я знаю другое доказательство, оно как раз проходит от 12 и меньше.
УдалитьРассмотрим те же самые частичные суммы Si, они все различные от 0 до 48. Рассмотрим величины Di=Si+Delta - они тоже все различные. Всего имеем 62 величины от 0 до 48+Delta. Если Delta<=12, то среди этого набора величин имеем две (как минимум) совпадающих. Очевидно они из разных наборов. Пусть Si=Dj=Sj+Delta. Это означает, что разность Si-Sj=Delta, что нам и требовалось.
Вот как раз мой вариант. Но...
Удалить>> Всего имеем 62 величины от 0 до 48+Delta. Если Delta<=12
Получается 61 величина при Delta=12.
>> имеем две (как минимум) совпадающих
Почему такой вывод?
Представим, что на каждой коробке мы пишем два числа. Первое - как раз та самая частичная сумма только без 0 так как для него нет коробки, второе - эта сумма + 12. Всего коробок 30. Получаем на 30 коробках 60 чисел в интервале от 1 до 48+12=60. Что возможно.
А для значения 11 уже получим 60 чисел из набора от 1 до 59. И здесь уже обязательно должно быть два одинаковых.
Если не учитывать сумму S0=0, то как раз и будет то, что у тебя написано. А ее учитывать можно. Во-первых, она ни с чем заведомо не совпадет. А во вторых, S0+Delta=Delta если совпадет с какой-то Si, то это и значит, что с 1ой коробки по i-ю набирается как раз Delta.
УдалитьЕсли мы вводим в картину S0, то получаем не 60 чисел, а 62 (правда в этом случае они не от 1, а от 0), что дает нам запас в ту самую единичку.
Все же непонятно заключение:
Удалить"Всего имеем 62 величины от 0 до 48+Delta. Если Delta<=12, то среди этого набора величин имеем две (как минимум) совпадающих."
Где в данном случае ограничение, с чем сравнивается значение 62? Почему тогда нельзя взять Delta=13? Будет 63 значения от 0 до 48+Delta.
Если Delta<=12, то числа все в интервале [0,60] - всего 61 значение.
УдалитьЕсли Delta=13 - этот фокус не проходит, потому что имеем все те же 62 значения, но уже в интервале [0,61] - теоретически несовпадение возможно (хотя и тут можно доказать, что такой ситуации не случится).
А, наконец догадался, что у меня в формулировке недостаточно точно :)
УдалитьПравильный вариант:
"Всего имеем 62 величины _из интервала_ от 0 до 48+Delta."
А с суммой 14 (или меньше) можно, получается, более сильный вариант доказать.
УдалитьРаскладываем шарики по 30 коробкам (в каждую не меньше одного), потом убираем первую коробку, и все равно найдется подпоследовательность с соответствующей суммой.