Математика · объяснение и практика

Когда принцип ящиков гарантирует совпадение

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

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Если семнадцать книг распределены по пяти полкам, хотя бы на одной полке окажется не меньше четырёх книг. Иначе на каждой было бы не больше трёх, а общее число не превысило бы пятнадцати. Распределение не обязано быть равномерным или случайным.

Как найти объекты и группы

В задаче сначала нужно точно определить, что распределяется и по каким категориям. Для дней рождения учеников группами могут быть двенадцать месяцев. У тринадцати учеников хотя бы два месяца рождения совпадут, потому что двенадцать разных групп не способны вместить по одному ученику все тринадцать объектов. Это не обещает конкретный совпавший месяц и не требует равных вероятностей месяцев.

Если категорий неограниченно много или один объект можно отнести сразу к нескольким группам без правила выбора, простая формулировка уже требует уточнения. В модели каждой книге назначается одна из пяти полок, каждому ученику — один календарный месяц рождения. Именно такое распределение делает подсчёт общих вместимостей определённым.

Как получить более сильный гарантированный минимум

Чтобы гарантировать хотя бы m объектов в одной из k групп, достаточно общего числа k·(m−1)+1. Если бы во всех группах было не больше m−1, всего получилось бы не больше k·(m−1). Дополнительный объект нарушает это предположение. Для пяти полок и четырёх книг на одной граница равна 5·3+1 = 16. Семнадцать также достаточно.

Недостаточность меньшего числа нужно показать возможным распределением. Пятнадцать книг можно разложить по три на каждую из пяти полок, и четырёх нигде не будет. Значит, шестнадцать является минимальным общим количеством для такой гарантии без иных ограничений. Различайте «достаточно» и «минимально достаточно»: второй вывод требует примера до границы.

Пример

Сколько учеников достаточно, чтобы гарантировать хотя бы троих с месяцем рождения одного названия?

Месяцев двенадцать. При 24 учениках можно иметь по два в каждом месяце. Двадцать пятый гарантирует хотя бы третьего в одной группе. Нельзя назвать заранее, в какой именно.

Почему гарантированное не равно вероятному

Совпадение может произойти и при меньшем числе объектов, но тогда оно ещё не неизбежно. Два ученика могут иметь один месяц рождения, однако могут иметь и разные. Принцип ящиков отвечает о худшем допустимом распределении, а не о наиболее частом. Вероятность раннего совпадения требует отдельной модели распределения и не получается одним делением количества на число групп.

В задачах о предметах одного цвета уточняйте, какое совпадение нужно. Два носка одного цвета не обязательно составляют подходящую по другим признакам пару, если условия различают размеры или сторону. Математическая гарантия относится только к явно выбранным категориям. Проверяйте свой вывод вопросом: какое распределение максимально откладывает требуемое совпадение? Если найденная граница превосходит его вместимость ровно на один объект, доказательство становится прозрачным.

От чтения к действию

А теперь — вы

Сколько объектов гарантирует хотя бы три объекта в одной из четырёх групп без других ограничений?

Частые вопросы

Требуется ли случайное распределение?

Нет. Принцип работает для любого распределения с заданными объектами и конечными группами.

Можно ли узнать, в какой группе будет совпадение?

В общем случае нет. Гарантируется существование хотя бы одной подходящей группы, а не её заранее определённое название.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться