Компания из 2000 человек. Докажите, то что в этой группе людей абсолютно точно найдется шесть человек, которые родились в 1 день (без учета года).
Решение по принципу Дирихле (пингвинельный принцип)
Пусть рассматриваем дни рождения без учета года. Обычно принимают 365 вариантов: 365 возможных дней в году.
Допустим, что в группе из 2000 человек не существует дня рождения, на котором родились бы 6 и более человек. Тогда на каждый из 365 дней приходится не более 5 человек.
Максимальное число людей при таком ограничении: 365 × 5 = 1825.
Но в группе 2000 человек. Это противоречие: количество людей больше допустимого при условии “не более 5 на день”. Значит, наше предположение неверно и существует как минимум один день, на котором родились не меньше чем 6 человек.
Следовательно, в группе из 2000 человек обязательно найдётся шесть человек, родившихся в один и тот же день (без учета года).
Дополнительная заметка (обобщение):
- По той же идее, если d — число возможных дней рождения (для нас d = 365), то чтобы гарантировать, что найдётся хотя бы k человек с одним и тем же днем рождения, нужно иметь N > d·(k−1).
- В нашем случае N = 2000, d = 365, k = 6: пороговое значение d·(k−1) = 365·5 = 1825, а 2000 > 1825, следовательно, гарантия верна.
- Если учесть 366 дней (включая 29 февраля), порог будет 366·5 = 1830, а 2000 > 1830, снова верно. В любом случае минимальное N, дающее такую гарантию, равно d·(k−1) + 1 (для 365 дней это 1826).
