Задачи по этой теме

Автор: Д. Калинин

Утверждение «среди любых трех целых чисел найдутся два числа одной четности» кажется очевидным, также как и утверждение «среди 13 человек найдутся двое, родившиеся в один месяц». И то, и другое можно обосновать разбором случаев. Но более грамотным будет построить рассуждение от противного. Для второго утверждения это будет выглядеть так:

«Предположим, что не найдется двух таких человек. Тогда в каждый из 12 месяцев родилось не более одного человека. Значит, имеется всего не более 12 человек, что противоречит условию задачи: 12 < 13.»

Такие рассуждения очень часто встречаются при решении задач, поэтому их выделили в отдельное утверждение, называемое принципом Дирихле. Классическая формулировка звучит так: « Если (n + 1) кроликов сидят в n ящиках, то найдётся ящик, в котором сидит, по крайней мере, два кролика». Доказательство этого утверждения также строится от противного:

«Предположим, что в каждом ящике сидит менее двух кроликов (один или ни одного). Тогда во всех n ящиках в совокупности сидит не более n кроликов. Противоречие.»

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

Пример 1.

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

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

Пример 2.

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

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

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

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

Пример 3.

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

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

Утверждение можно доказать, проводя сразу рассуждения от противного. Пусть конфет каждого сорта не более 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). По принципу Дирихле в любой момент турнира найдется два игрока, сыгравших одинаковое количество партий.

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