Клітки для кроликів – принцип Діріхле

Кролики у клітках - принцип ДіріхлєОдна з найвідоміших задач комбінаторики про кроликів чи голубів, яких розсаджують по клітках.

Чи можна п’ять кроликів ( чи голубів) розсадити у чотири клітки так, щоб у кожній було рівно по одному кролику (голубу)?

Зрозуміло, що у такому випадку хоча б у одній клітці буде більше, ніж один кролик!

Німецький математик Петер Діріхле сформулював комбінаторне твердження, яке має таке найпоширеніше формулювання:

Припустимо, деяке число кроликів розсаджені в клітках. Якщо число кроликів більше, ніж число кліток, то хоча б у одній з кліток буде більше одного кролика.

У загальному вигляді можлива така інтерпретація:

Припустимо, mкроликів розсаджені в nклітках. Тоді в одній клітці міститься не менше [m/n] кроликів, а також хоч би в одній іншій клітці міститься не більше [n/m] кроликів.

Розглянемо деякі задачі, що розв’язуються за допомогою принципу Діріхле.

Задача 1

У класі 26 учнів, доведіть, що у році є місяць, коли святкують день народження точно 3 учні?

Розв’язання

Припустимо, що ми маємо найменш сприятливий варіант, коли кожного місяця є учні, що святкують день народження. Оскільки місяців 12, то якщо кожного місяця буде по два іменинника, тоді:

12*2=24, 26-24=2.

Отже у цих двох учнів день народження припадає на місяць, у якому вже народилося два учні, тобто є хоча б один місяць, коли народилося 3 учні!

Задача 2

У лісі ростуть 800000 ялин. На кожній ялині – не більше 500000 голок. Доведіть, що існує хоча б дві ялини з однаковим числом голок?

Розв’язання

Припустимо супротивне, що у цьому лісі не існує дві ялини з однаковим числом голок. Тоді існує не більше однієї ялини (одна, чи жодної), що має одну голку.

Аналогічно: існує не більше однієї ялини (одна, чи жодної) з двома голками…, існує не більше однієї ялини (одна, чи жодної) з 499999 голками, не більше однієї ялини (одна, чи жодної) з 500000 голками.

Таким чином не більше, ніж 500000 ялин мають кількість голок від 1 до 500000.

Оскільки у лісі ростуть 800000 ялин, і кожна має не більше ніж 500000 голок, то з цього випливає, що знайдеться хоча б дві ялини з однаковим числом голок!

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *