Принцип Дирихле

Шаг

Инструкция для учащихся

1.

2.

Если устали читать, то основные понятия по теме вы узнаете, просмотрев видеоуро https://yadi.sk/i/Mar7SUd2GejxZQ

https://yadi.sk/i/ZsYHJ6FTwE1tEg

3.

Пример 1.

Докажите, что никакая прямая не может пересекать все три стороны треугольника.

Решение: Прямая делит плоскость на две полуплоскости, которые мы назовем «клетками». Три вершины треугольника назовем «кроликами». По принципу Дирихле, «найдется клетка, в которой сидит по крайней мере два кролика», то есть найдутся две вершины, лежащие в одной полуплоскости относительно данной прямой. Сторона, соединяющая эти вершины, не пересекает данную прямую.

Пример 2.

Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.

Решение: Рассмотрим три грани куба, имеющие общую вершину. Назовем их «кроликами», а данные цвета — «клетками». По принципу Дирихле, найдутся две грани, окрашенные в один цвет. Они и будут соседними.

Аналогично доказывается общая формулировка принципа Дирихле: «Если n кроликов сидят в k ящиках, то найдётся ящик, в котором сидят не меньше чем n / k кроликов».

Немного иначе это утверждение выглядит так: «Если nk + 1 кроликов сидят в k ящиках, то найдётся ящик, в котором сидит, по крайней мере, (n + 1) кроликов».

Пример 3.

Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?

Решение: Пусть «клетками» у нас будут сорта конфет, а «кроликами» -сами конфеты. По принципу Дирихле найдется «клетка», в которой не менее 25 / 3 «кроликов». Так как 8 

Утверждение можно доказать, проводя сразу рассуждения от противного. Пусть конфет каждого сорта не более 9, то есть не превышает восьми. Тогда всего конфет не больше 3 × 8 = 24, а по условию их 25. Противоречие.

Пример 4.

В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок.

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

Пример 5.

В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка — точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.

Решение: Весь ковер можно накрыть такими 25-ю заплатами. По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок.

Иногда принцип Дирихле не работает «впрямую», что требует дополнительных соображений.

Пример 6.

Несколько футбольных команд проводят турнир в один круг. Докажите, что в любой момент турнира найдутся две команды, сыгравшие к этому моменту одинаковое число матчей.

Решение: Пусть всего n шахматистов. Тогда каждый мог сыграть от 0 до n - 1 партий: всего n вариантов. Казалось бы, что принцип Дирихле не работает: у нас имеется n различных шахматистов и n различных количеств сыгранных партий.

Заметим, однако, что если какой-то шахматист не сыграл ни одной партии, то не найдется шахматиста, сыгравшего все партии. То есть не может быть ситуации, когда есть игрок, сыгравший 0 партий, и игрок, сыгравший n - 1 партию. Значит, различных количеств сыгранных партий в любой момент турнира может быть не более n - 1 (от 0 до n - 2 или от 1 до n - 1). По принципу Дирихле в любой момент турнира найдется два игрока, сыгравших одинаковое количество партий.

4.

Множество задач для самостоятельного решения

https://problems.ru/view_by_subject_new.php?parent=352

https://uni.bsu.by/arrangements/video/pdf/zadan_prDirichle.pdf

5.

Урок закончился, а что осталось, поделитесь своими впечатлениями от занятия!