Математика · объяснение и практика
Когда принцип ящиков гарантирует совпадение
Доказываем неизбежное совпадение при распределении объектов по группам, отличаем гарантированный минимум от вероятности и проверяем достаточное количество.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
Если семнадцать книг распределены по пяти полкам, хотя бы на одной полке окажется не меньше четырёх книг. Иначе на каждой было бы не больше трёх, а общее число не превысило бы пятнадцати. Распределение не обязано быть равномерным или случайным.
Как найти объекты и группы
В задаче сначала нужно точно определить, что распределяется и по каким категориям. Для дней рождения учеников группами могут быть двенадцать месяцев. У тринадцати учеников хотя бы два месяца рождения совпадут, потому что двенадцать разных групп не способны вместить по одному ученику все тринадцать объектов. Это не обещает конкретный совпавший месяц и не требует равных вероятностей месяцев.
Если категорий неограниченно много или один объект можно отнести сразу к нескольким группам без правила выбора, простая формулировка уже требует уточнения. В модели каждой книге назначается одна из пяти полок, каждому ученику — один календарный месяц рождения. Именно такое распределение делает подсчёт общих вместимостей определённым.
Как получить более сильный гарантированный минимум
Чтобы гарантировать хотя бы m объектов в одной из k групп, достаточно общего числа k·(m−1)+1. Если бы во всех группах было не больше m−1, всего получилось бы не больше k·(m−1). Дополнительный объект нарушает это предположение. Для пяти полок и четырёх книг на одной граница равна 5·3+1 = 16. Семнадцать также достаточно.
Недостаточность меньшего числа нужно показать возможным распределением. Пятнадцать книг можно разложить по три на каждую из пяти полок, и четырёх нигде не будет. Значит, шестнадцать является минимальным общим количеством для такой гарантии без иных ограничений. Различайте «достаточно» и «минимально достаточно»: второй вывод требует примера до границы.
Пример
Сколько учеников достаточно, чтобы гарантировать хотя бы троих с месяцем рождения одного названия?
Месяцев двенадцать. При 24 учениках можно иметь по два в каждом месяце. Двадцать пятый гарантирует хотя бы третьего в одной группе. Нельзя назвать заранее, в какой именно.
Почему гарантированное не равно вероятному
Совпадение может произойти и при меньшем числе объектов, но тогда оно ещё не неизбежно. Два ученика могут иметь один месяц рождения, однако могут иметь и разные. Принцип ящиков отвечает о худшем допустимом распределении, а не о наиболее частом. Вероятность раннего совпадения требует отдельной модели распределения и не получается одним делением количества на число групп.
В задачах о предметах одного цвета уточняйте, какое совпадение нужно. Два носка одного цвета не обязательно составляют подходящую по другим признакам пару, если условия различают размеры или сторону. Математическая гарантия относится только к явно выбранным категориям. Проверяйте свой вывод вопросом: какое распределение максимально откладывает требуемое совпадение? Если найденная граница превосходит его вместимость ровно на один объект, доказательство становится прозрачным.
От чтения к действию
А теперь — вы
Частые вопросы
Требуется ли случайное распределение?
Нет. Принцип работает для любого распределения с заданными объектами и конечными группами.
Можно ли узнать, в какой группе будет совпадение?
В общем случае нет. Гарантируется существование хотя бы одной подходящей группы, а не её заранее определённое название.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Когда порядок выбранных предметов не создаёт новый вариант
Считаем группы без должностей и порядка, объясняем деление на перестановки внутри выбранной группы и отличаем сочетания от упорядоченного выбора.
Открыть темуКак посчитать кратные внутри целочисленного отрезка
Считаем целые кратные положительного числа на отрезке без полного перечисления: вычитаем накопленные количества и точно учитываем включённые границы.
Открыть тему