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

принципом Дирихле. Классическая формулировка звучит так: «Если (n + 1) кроликов сидят в 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). По принципу Дирихле в любой момент турнира найдется два игрока, сыгравших одинаковое количество партий.

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

Самая популярная задача на прямое применение принципа Дирихле такова: на Земле живет 3 млрд. человек, у каждого на голове – не более миллиона волос. Нужно доказать, что обязательно найдутся два человека с одинаковым числом волос. Приняв в качестве «классов» возможное число волос от 0 до 1 000 000 (всего 1 000 001 класс), а в качестве «предметов» население Земли (всего 3 000 000 000 предметов) и применив принцип Дирихле, получим, что обязательно найдутся, по крайней мере, 2 000 людей, имеющих одинаковое число волос на голове.

Задача 1. В розыгрыше кубка по футболу (в один круг) участвуют 30 команд. Доказать, что в любой момент найдутся две команды, сыгравшие одинаковое число игр.

Решение. Рассмотрим два случая.

I. Хотя бы одна из 30 команд не сыграла еще ни одной игры.

II. Каждая команда сыграла хотя бы одну игру.

Докажем утверждение для I-го случая.

Так как хотя бы одна из 30 команд не сыграла еще ни одной игры, то число игр у любой команды не более 28, то есть возможное число игр у каждой из команд может быть: 0, 1, 2, …, 28 (всего 29 чисел), а команд по условию 30. Тогда по принципу Дирихле, приняв в качестве «классов» числа проведенных игр (всего 29 «классов»), а в качестве «предметов» - команды (всего 30 «предметов»), получим, что хотя бы 2 команды будут соответствовать одному числу проведенных игр, а значит, хотя бы 2 команды сыграли одинаковое число игр.

Докажем утверждение для II-го случая.

Так как каждая из 30 команд сыграла хотя бы одну игру, то число проведенных игр может принимать значения: 1, 2, …, 29 (всего 29), я команд 30, тогда по принципу Дирихле найдутся хотя бы 2 команды, сыгравшие одинаковое число игр.

Задача 2. Доказать, что среди шести любых чисел найдутся два, разность которых делится на пять.

Решение.

I. Из теории делимости известно, что разность чисел (a –b) делится на m тогда и только тогда, когда a и b при делении на m дают одинаковые остатки. Учитывая это утверждение, переформулируем задачу:

II. Доказать, что среди шести любых чисел найдутся два числа, которые при делении на пять, дают одинаковые остатки.

III. Докажем это утверждение.

По теореме о делении с остатком, при делении числа на пять может быть один из пяти остатков: 0, 1, 2, 3, 4. При этом рассматриваются шесть любых чисел.

6>5, по принципу Дирихле получаем, что, приняв в качестве «классов» – остатки, в качестве «предметов» - числа, учитывая, что хотя бы два числа из шести имеют одинаковые остатки при делении на пять, а значит, их разность делится на пять.

Задача 3. Каждая из девяти прямых разбивает квадрат на два четырехугольника, площади которых относятся как 2:3. Докажите, что, по крайней мере, три из этих девяти прямых проходят через одну точку.

Решение.

1. Каждая из девяти прямых разбивает квадрат либо на два прямоугольника, либо на две трапеции.

2. Площадь трапеции равна , где h – высота трапеции (в нашем случае сторона квадрата), C – длина средней линии трапеции (отрезок на средней линии квадрата).

3. Так как по условию площади получившихся трапеций или прямоугольников делятся как 2:3, то в том же отношении (п.2) прямая делит и среднюю линию квадрата.

4. Таких точек, которые делят одну из средних линий квадрата в отношении 2:3 всего 4 (см. рис.), прямых по условию 9, и каждая из них должна пройти через одну из этих точек.

5. И так «классов» – 4, «предметов» –9>2×4, тогда по принципу Дирихле, найдется три прямых проходящих через одну из этих четырех точек.

Поиск по сайту: