Принцип Діріхле — потужний інструмент для вирішення комбінаторних задач
Що таке принцип Діріхле?
Принцип Діріхле — це комбінаторне твердження, яке стверджує, що якщо у нас є $n$ предметів і $m$ коробок, причому $n > m$, то принаймні одна коробка міститиме більше одного предмета. Іншими словами, якщо ми розподілимо $n$ предметів по $m$ коробках, то принаймні одна коробка буде переповнена.
Цей принцип можна застосувати для вирішення багатьох комбінаторних задач. Наприклад, ми можемо використовувати його для того, щоб довести, що існує не менше двох людей з однаковим днем народження у групі з $23$ людей. Адже у нас є $365$ можливих днів народження, а в групі $23$ людини. Отже, за принципом Діріхле, принаймні дві людини в групі мають однаковий день народження.
Різні формулювання принципу Діріхле
Принцип Діріхле можна сформулювати декількома різними способами. Ось деякі з них:
- Якщо $n$ голубів розмістити в $m$ голубниках, то принаймні один голубник міститиме більше одного голуба.
- Якщо $n$ предметів розподілити по $m$ коробках, то принаймні одна коробка міститиме більше одного предмета.
- Якщо $n$ людей займуть $m$ кімнат, то принаймні одна кімната буде зайнята більше ніж однією людиною.
Застосування принципу Діріхле
Принцип Діріхле можна застосувати для вирішення багатьох комбінаторних задач. Ось деякі приклади:
- Доведіть, що у групі з $23$ людей принаймні дві людини мають однаковий день народження.
- Доведіть, що серед будь-яких $6$ цілих чисел знайдуться щонайменше два, різниця між якими кратна $5$.
- Доведіть, що серед будь-яких $10$ точок на площині знайдуться щонайменше три точки, які утворюють рівносторонній трикутник.
Висновок
Принцип Діріхле — це потужний інструмент для вирішення комбінаторних задач. Він може бути використаний для того, щоб довести багато важливих тверджень. За допомогою принципу Діріхле ми можемо, наприклад, довести, що у будь-якій групі людей знайдуться дві людини з однаковим днем народження, або що серед будь-якого набору цілих чисел можна знайти два числа, різниця між якими кратна $5$.
Часто задавані питання
- Що таке принцип Діріхле?
- Як можна сформулювати принцип Діріхле?
- Де застосовується принцип Діріхле?
- Наведіть приклади задач, які можна вирішити за допомогою принципу Діріхле.
- Як довести принцип Діріхле?