Почему совпадение неизбежно
Предположим обратное: в каждой из четырёх коробок лежит максимум один предмет. Тогда всего предметов не больше четырёх. Но по условию их пять. Противоречие показывает, что хотя бы одна коробка содержит два предмета или больше. При этом мы не знаем, какая именно коробка переполнится.
Например, у 13 человек обязательно найдутся двое, родившиеся в одном месяце: людей 13, а месяцев 12. У 12 человек такой гарантии нет — допустим расклад, при котором каждый родился в отдельном месяце. Этот пример одновременно показывает, почему число 13 минимально.
Как найти гарантию тройки или четвёрки
Чтобы не образовалась тройка одного цвета, из мешка с носками двух цветов можно достать максимум по два носка каждого цвета, всего четыре. Пятый носок создаст тройку. Это гарантия при условии, что в мешке достаточно носков для пяти вытягиваний.
Общий приём: при k группах расклад без группы из r объектов может содержать не больше k × (r − 1) объектов. Следующий, то есть k × (r − 1) + 1, уже гарантирует нужное количество хотя бы в одной группе. Для четырёх объектов одного цвета при трёх цветах получится 3 × 3 + 1 = 10.
- Определите число групп k.
- Разрешите каждой группе набрать r − 1 объектов.
- Посчитайте максимальный общий размер такого расклада.
- Добавьте один объект и объясните, почему он нарушает ограничение.
Неочевидные коробки: остатки от деления
У целого числа при делении на 5 возможны пять остатков: 0, 1, 2, 3 и 4. Поэтому среди любых шести целых чисел найдутся два с одинаковым остатком. Их разность делится на 5: если числа имеют вид 5a + r и 5b + r, разность равна 5(a − b).
Здесь коробками служат классы остатков. Сами числа могут быть очень большими, но их размер не важен. Принцип позволяет доказать существование нужной пары без полного перебора. Для конкретного набора 11, 17, 23, 29, 35, 41 совпадение дают 11 и 41: разность 30 делится на 5.
Что принцип не обещает
Гарантия пары любого цвета не равна гарантии пары выбранного цвета. Если нужны именно красные носки, противник может сначала выдавать все синие. В этом случае нужно знать запас синих и наличие как минимум двух красных; одного числа цветов недостаточно.
Проверьте себя на задаче: сколько человек гарантируют троих, родившихся в одном месяце? Без тройки каждый из 12 месяцев может собрать по два человека: 24. Поэтому ответ — 25. Для доказательства минимальности опишите допустимый расклад 24 человек, по двое на каждый месяц.
Коротко о частом
Вопросы и ответы
Принцип Дирихле и худший случай — одно и то же?
Принцип Дирихле — конкретное утверждение о распределении объектов. Метод худшего случая шире. Во многих задачах на гарантированное совпадение они используются вместе.
Можно ли узнать, какая группа окажется самой большой?
Сам принцип доказывает наличие достаточно большой группы, но не определяет её название. Для этого нужны дополнительные сведения.