Если у нас имеется сколько-то клеток, а кроликов на одного больше, то после рассаживания кроликов по клеткам найдётся клетка, где сидит по крайней мере два кролика

Это и есть принцип Дирихле. Его можно записать и иначе на «математическом» языке:

После рассаживания в n клетках n + 1 кролика найдётся клетка, где сидит, по крайней мере, два кролика.

Попробуем обобщить принцип Дирихле,

Пример 2. Можно ли рассадить 9 кроликов в 4 клетки так, чтобы в каждой клетке было не более двух кроликов?

Решение. Этого сделать нельзя: по крайней мере в одной клетке будет сидеть не меньше трёх кроликов. Отметим, что их может быть и больше трёх (если, например, посадить в 3 клетки по одному кролику, а в четвёртую всех остальных).

Пример 3. Можно ли рассадить в 20 клеток 101 кролика так,

чтобы в каждой клетке было не более 5 кроликов?

Решение. Нельзя. В некоторой клетке будет не меньше шести кроликов.

Обобщение принципа Дирихле. В данные n клеток мы разместили nk + 1 кролика. Тогда найдётся клетка, где сидит не менее k + 1 кролика.

Пример 4. В классе учится 29 человек. Серёжа допустил в диктанте 13 ошибок, и никто другой не сделал большего числа ошибок. Доказать, что по крайней мере трое учеников сделали одинаковое количество ошибок.

Решение: Пусть «клетки» - это количество ошибок, которые могли сделать школьники: 0, 1, 2, ···, 13. Их 14. За «кроликов» примем учеников, писавших диктант. Их 29 = 14 · 2 + 1. Тогда по принципу Дирихле (а точнее, по его обобщению) найдётся «клетка», в которой сидит не меньше трёх «кроликов», а это и означает, что найдётся трое школьников, сделавших одинаковое количество ошибок.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



double arrow
Сейчас читают про: