Условие
У 25 человек известен только месяц рождения. Докажите, что хотя бы трое родились в одном месяце. Можно ли гарантировать четверых?
Решение по шагам
Есть 12 месяцев. Если бы в каждом было не больше двух человек, всего получилось бы не больше 24. Это противоречит условию, поэтому один месяц содержит как минимум троих.
Четверых гарантировать нельзя: можно разместить по два человека в каждом из 12 месяцев и добавить последнего в один месяц. Максимальная группа тогда имеет ровно три человека. Мы доказали и нижнюю гарантию, и её достижимость.
Проверка результата
Распределение 3,2,2,2,2,2,2,2,2,2,2,2 содержит 25 человек и не имеет группы из четырёх. Верхняя оценка при ограничении «не более двух» равна 12·2=24.
Типичная ошибка
Равномерность месяцев и независимость дат не нужны. Это утверждение о любом распределении, а не оценка вероятности совпадения.
Что даёт этот метод
Для N объектов в k группах существует группа размера не меньше ⌈N/k⌉. Чтобы гарантировать r объектов в одной группе, достаточно N>k(r−1).
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.