Question

Семь гномов собрали 29 грибов,причём ни один из них не принёс пустой корзины.Доказать,что хотя бы два гнома собрали одинаковое количество грибов,если никто более 7 грибов не нашёл.

Answer 1

Никто не принес пустой корзины, значит каждый мог собрать: 1, 2, 3, 4, 5, 6 или 7 грибов.

Но они не могли собрать все разное число грибов, т. к. иначе, они собрали бы 1+2+3+4+5+6+7=28 грибов, значит какие-то 2 гнома собрали одинаковое число грибов, ч. т. д.

Answer 2

Давайте рассмотрим все возможные варианты количеств грибов, которые могут быть собраны каждым гномом: 1. Первый гном собрал 0 грибов, а остальные гномы – по 29 грибов каждый. 2. Первый гном собрал 1 гриб, а остальные гномы – по 28 грибов каждый. 3. Первый гном собрал 2 гриба, а остальные гномы – по 27 грибов каждый. 4. И так далее, до ситуации, когда первый гном собрал 29 грибов, а остальные гномы – по 0 грибов каждый. Всего у нас 30 возможных вариантов. Теперь заметим, что если мы вычтем из суммы грибов, собранных все гномами вместе, 7 грибов (так как никто не нашел больше 7 грибов), то мы получим величину от 0 до 23. То есть, у нас есть всего 24 таких возможных различных значений величины g, обозначающей количество грибов, которое может быть собрано каждым гномом, если никто более 7 грибов не нашел. Однако, у нас было 30 возможных вариантов количеств грибов, собранных первым гномом. Значит, по принципу Дирихле, мы должны выбрать какой-то вариант грибов, который повторяется хотя бы дважды (если таких вариантов нет, то каждый вариант должен был бы повторяться ровно один раз, что нарушает условие задачи). Это значит, что какие-то два гнома собрали одинаковое количество грибов. Таким образом, мы доказали, что хотя бы два гнома обязательно собрали одинаковое количество грибов при данном условии.