среда, 9 июля 2014 г.

48 шариков в 30 коробках

Перед вами в ряд выставлено 30 коробок. У вас в наличии есть 48 шариков. Все имеющиеся шарики нужно разложить по коробкам. Их число в коробке может быть произвольным, но в каждой должен оказаться хотя бы один шарик. Докажите, что в итоге найдётся последовательность стоящих друг за другом коробок, суммарное число шариков в которых будет равным 11.
Картонные коробки
update
Первый - Илья.
Ответ
Запишем на каждой коробке суммарное число шариков в ней и во всех предыдущих. Получим 30 чисел из диапазона от 1 до 48. Далее на каждой коробке запишем ещё по одному числу, которое равно сумме уже написанного и числа 11. Получим ещё 30 чисел, максимальное из которых 48+11=59. Таким образом, мы получили 60 чисел из диапазона от 1 до 59. То есть два каких-то числа будут равны между собой. А равенство двух чисел означает, что в соответствующей последовательности коробок лежит ровно 11 шариков.

23 комментария:

  1. Очень интересная задача. Особенно если у нее есть красивое решение :)

    Пока не нашел, пусть по которому иду как-то слишком трудоемким оказался.

    ОтветитьУдалить
    Ответы
    1. Решение довольно интересное. И несложное для понимания, но ведь нужно для него догадаться...

      Удалить
  2. Мне подсказали красивое решение. Не знаю, стоит ли выкладывать... :)
    Сам бы до такого почти наверняка не додумался :)

    ОтветитьУдалить
    Ответы
    1. Задача вроде бы интересна публике, пускай ещё погадают :)

      Удалить
  3. кладем по одному шарику. У нас 19 "11цаток" и остается 18 шариков. С каждым новым шариком становится на одну "11цатку" меньше. Значит одна останется

    ОтветитьУдалить
    Ответы
    1. а что такое 11цтка в данном случае ?

      Удалить
    2. просто добавляя шарики в 11-ю и в 22-ю коробку вы портите все свои 11цтки

      Удалить
  4. Давайте попробуем так:
    так как в каждой коробке должен быть хотя б один шарик, то у нас остается 48-30=18 шариков, которые определяют нашу комбинацию расположения шариков по коробкам. Но т.к. коробок 30, а таких вот шариков всего 18, то у нас остается 30-18=12 коробок которые так и останутся с одним шариком.

    дальше додумаю завтра, что-то не приходит решение в голову :)

    ОтветитьУдалить
    Ответы
    1. Я шел примерно таким путем, но это получается трудоемко.
      Еще можно сообразить, что может быть не больше одной коробки, в которой больше 11 шариков, и если такая есть, то среди остальных получается еще больше (22 кажется) таких, в которых по одному.

      Это можно развивать дальше, но много вариантов :)

      Удалить
  5. Кстати, если я не путаю, при тех же условиях обязательно найдется последовательность коробок с суммарным количеством шариков 12.

    ОтветитьУдалить
    Ответы
    1. А также 13, 14 и 15. То же верно для любых меньших значений.
      Если я не путаю, опять же.

      Удалить
    2. Вот как раз в меньшую сторону получается, а для 12 и больше можно доказать обратное.

      Удалить
    3. Контрпример есть?
      У меня вроде корректное доказательство получилось. Но пойду проверю.

      Удалить
    4. так покажи нам доказательство, мы быстро проверим )

      Удалить
    5. Ну раз просите :)

      Скажем, для 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 есть очевидный контрпример, конечно :)

      Удалить
    6. Похоже на правду.
      Моё доказательство не настолько общее. По нему 12 уже проходит. Хотя конкретных примеров с помощью него составить нельзя.

      Удалить
    7. Я знаю другое доказательство, оно как раз проходит от 12 и меньше.

      Рассмотрим те же самые частичные суммы Si, они все различные от 0 до 48. Рассмотрим величины Di=Si+Delta - они тоже все различные. Всего имеем 62 величины от 0 до 48+Delta. Если Delta<=12, то среди этого набора величин имеем две (как минимум) совпадающих. Очевидно они из разных наборов. Пусть Si=Dj=Sj+Delta. Это означает, что разность Si-Sj=Delta, что нам и требовалось.

      Удалить
    8. Вот как раз мой вариант. Но...
      >> Всего имеем 62 величины от 0 до 48+Delta. Если Delta<=12
      Получается 61 величина при Delta=12.
      >> имеем две (как минимум) совпадающих
      Почему такой вывод?
      Представим, что на каждой коробке мы пишем два числа. Первое - как раз та самая частичная сумма только без 0 так как для него нет коробки, второе - эта сумма + 12. Всего коробок 30. Получаем на 30 коробках 60 чисел в интервале от 1 до 48+12=60. Что возможно.
      А для значения 11 уже получим 60 чисел из набора от 1 до 59. И здесь уже обязательно должно быть два одинаковых.

      Удалить
    9. Если не учитывать сумму S0=0, то как раз и будет то, что у тебя написано. А ее учитывать можно. Во-первых, она ни с чем заведомо не совпадет. А во вторых, S0+Delta=Delta если совпадет с какой-то Si, то это и значит, что с 1ой коробки по i-ю набирается как раз Delta.
      Если мы вводим в картину S0, то получаем не 60 чисел, а 62 (правда в этом случае они не от 1, а от 0), что дает нам запас в ту самую единичку.

      Удалить
    10. Все же непонятно заключение:

      "Всего имеем 62 величины от 0 до 48+Delta. Если Delta<=12, то среди этого набора величин имеем две (как минимум) совпадающих."

      Где в данном случае ограничение, с чем сравнивается значение 62? Почему тогда нельзя взять Delta=13? Будет 63 значения от 0 до 48+Delta.

      Удалить
    11. Если Delta<=12, то числа все в интервале [0,60] - всего 61 значение.

      Если Delta=13 - этот фокус не проходит, потому что имеем все те же 62 значения, но уже в интервале [0,61] - теоретически несовпадение возможно (хотя и тут можно доказать, что такой ситуации не случится).

      Удалить
    12. А, наконец догадался, что у меня в формулировке недостаточно точно :)

      Правильный вариант:
      "Всего имеем 62 величины _из интервала_ от 0 до 48+Delta."

      Удалить
    13. А с суммой 14 (или меньше) можно, получается, более сильный вариант доказать.
      Раскладываем шарики по 30 коробкам (в каждую не меньше одного), потом убираем первую коробку, и все равно найдется подпоследовательность с соответствующей суммой.

      Удалить