Принцип Дирихле и его применение при решении задач

Основы теории. Принцип Дирихле выражает соотношение между двумя множествами. Существует несколько формули­ровок данного принципа. Самая популярная следующая: «Ес­ли в п клетках сидит т зайцев, причем т > п, то хотя бы в од­ной клетке сидят, по крайней мере, два зайца». Доказывается данный принцип Дирихле легко, методом доказательства от противного. Некоторые задачи на применение данного прин­ципа также можно решить, используя метод доказательства от противного, но не все.

На первый взгляд, непонятно, почему это совершенно оче­видное предложение, тем не менее, является мощным матема­тическим методом решения задач, причем самых разнообраз­ных. Всё дело оказывается в том, что в каждой конкретной задаче нелегко понять, что же здесь выступает в роли «зай­цев», а что — в роли «клеток». И почему надо, чтобы «зайцев» было больше, чем «клеток». Выбор «зайцев» и «клеток» часто неочевиден. Далеко не всегда по формулировке задачи можно определить, что следует применить принцип Дирихле. Глав­ное же достоинство данного метода решения состоит в том, что он дает неконструктивное решение, (то есть мы знаем, что такие клетки есть, но где именно они находятся, часто указать не можем); попытка же дать конструктивное доказательство приводит к большим трудностям.

Рассмотрим другие формулировки принципа Дирихле:

«Пусть в п клетках сидят т зайцев, причем п> т. Тогда найдется хотя бы одна пустая клетка». (Доказывается анало­гично — методом от противного);

«Если т зайцев сидят в п клетках, то найдется клетка, в которой сидят не меньше, чем зайцев, и найдется клетка, в которой сидят не больше, чем зайцев»;

«Если т зайцев съели п килограммов травы, то какой-то заяц съел не менее килограммов травы и какой-то заяцсъел не больше килограммов (а если кто-то съел больше среднего, то кто-то съел меньше среднего)» (непрерывный принцип),

«Если в п клетках сидят т зайцев и , то в какой-то из клеток сидят, по крайней мере, заяц» (обобщенный принцип)

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

Сформулируем дан­ные утверждения (все они легко доказываются методом от противного):

1. Если на отрезке длиной 1 расположено несколько отрез­ков, сумма длин которых больше 1, то, по крайней мере, два из них имеют общую точку.
2. Если на окружности радиуса 1 расположено несколько дуг, сумма длин которых больше 2π, то, по крайней мере, две из них имеют общую точку.
3. Если внутри фигуры площадью 1 расположено несколько фигур, сумма площадей которых больше 1, то, по крайней мере, две из них имеют общую точку.

Примеры задач, решаемых данным методом.

Задача №1. Внутри равностороннего треугольника со стороной 1 см расположено 5 точек. Докажите, что расстояние между неко­торыми двумя из них меньше 0,5 см.

Решение.На примере решения этой задачи очень хорошо видны все досто­инства принципа Дирихле. Итак, при решении сначала надо выбрать что-то за «зайцев». Так как в условии задачи фигури­рует число «5», то пусть 5 точек будут «зайцами». Так как «клеток» должно быть меньше, и чаще всего на 1, то их долж­но быть 4. Как получить эти 4 «клетки»? Так как в условии задачи есть еще 2 числа: 1 и 0,5; причем второе меньше перво­го в 2 раза, то можно получить 4 «клетки», разбив равносто­ронний треугольник с помощью проведения средних линий. Тогда получим 4 равносторонних треугольника со сторонами по 0,5 см, которые и будут у нас «клетками».

Так как «зайцев» — 5, «клеток» — 4 и 5 > 4, то по прин­ципу Дирихле найдется «клетка» — равносторонний тре­угольник со стороной 0,5 см, в который попадут не менее 2 «зайцев» — точек. А так как все 4 треугольника равны и рас­стояние между точками в любом треугольнике будет меньше, чем 0,5 см, то мы доказали, что между некоторыми 2 точками из 5 расстояние будет меньше, чем 0,5 см.

Замечание. Можно разбить треугольник и на другие фигу­ры (в этих случаях придется вместо средних линий треуголь­ника (одной, двух или трех) проводить соответственно дуги радиуса 0,5 см с центром в вершинах треугольника).

Возможные варианты получения «клеток» показаны на рисунках

Задача №2. Дано 12 целых чисел. Докажите, что из них можно вы­брать 2, разность которых делится на 11.

Решение, Примем числа за «зайцев». Так как их 12, то «клеток» должно быть меньше. Пусть «клетки» — это остатки от деления целого числа на 11. Всего «клеток» будет 11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Тогда по принципу Дирихле найдется «клетка», в которой будут сидеть не менее чем 2 «зайца», то есть найдутся 2 целых числа с одним остатком. А разность 2 чисел с одинаковым остатком от деления на 11, будет де­литься на 11.

Задача №3. В ковре размером 4x4 метра моль проела 15 дырок. До­кажите, что из него можно вырезать коврик размером 1x1 метр, не содержащий внутри себя дырок. (Дырки можно счи­тать точечными).

Решение. Разрежем ковёр на 16 ковриков размерами 1x1 метр. Так как ковриков — «клеток» — 16, а дырок — «зайцев» — 15, то найдется хотя бы одна «клетка», в которой не будет «зайцев», то есть найдётся коврик без дырок внутри. Здесь мы применили другую формулировку принципа Дирихле.

Задача №4. В классе 27 учеников. Найдётся ли месяц, в котором от­мечают свои дни рождения не меньше, чем три ученика этого класса.

Решение. В году 12 месяцев. Обозначим их за «клетки», аучеников за «зайцев». Так как 27 > 12 • 2 + 1, то по обобщенному принципу Дирихле найдется «клетка», в которой сидят не менее 3 «зайцев», то есть найдется месяц, в котором дни рождения празднуют не менее 3 учеников.

Замечание. Задачу можно решить, применяя метод от про­тивного.

Задача №5. 16 учеников сидят за круглым столом, причем больше половины из них девушки. Докажите, что какие-то 2 девушки сидят напротив друг друга.

Решение. Образуем 8 пар, в каждую пару включим учени­ков, сидящих друг против друга. Примем за «клетки» — пары, а за «зайцев» — девушек. Так как девушек больше половины, то есть восьми, то найдется «клетка» (пара), в которой будут находиться 2 девушки.

Задача №6. Плоскость раскрашена в 2 цвета. Можно ли всегда най­ти 2 точки, расположенные на расстоянии 1 метра друг от дру­га, окрашенные в одинаковый цвет?

Решение. Так как цветов — 2, то надо рассмотреть фигуру, в которой точек больше 2. Лучше всего для этого подойдет равносторонний треугольник со стороной 1 метр. У него 3 вершины. Принимая вершины треугольника за «зайцев», а цвета за «клетки», имеем: 3 > 2. Тогда по принципу Дирихле найдутся 2 вершины треугольника, расположенные на рас­стоянии 1 метра друг от друга, окрашенные в один цвет.

Задача №7. Каждая точка плоскости окрашена в один из двух цветов. Известно, что у любого правильного треугольника со стороной 1 имеются вершины обоих цветов.

а) Докажите, что найдется правильный треугольник со стороной , все вершины которого одинакового цвета.

б) Приведите пример раскраски плоскости, удовлетворяющей условию задачи.

Решение.

Возьмем отрезок АВ длиной 2 с разноцветными концами. Такой отрезок существует: в противном случае все точки окружности радиуса 2 с центром в произвольной точке О были бы окрашены в тот же цвет, что и точка О, а всевозможные окружности радиуса 2 с центром на окружности заполнили бы круг радиуса 4 с центром О, все точки которого были бы одного цвета, что невозможно. Пусть цвет точки С – середины отрезка АВ – совпадает с цветом точки А. Построим правильные треугольники ACDи ACEпо разные стороны от прямой АВ. По условию задачи точки Dи Е окрашены в тот же цвет, что и точка В, поэтому треугольник BDEбудет искомым.

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

Задача №8.Докажите, что если имеется 100 целых чисел , то из них можно выбрать несколько чисел (может быть одно), сумма которых делится на 100.

Решение.

Рассмотрим суммы

Если хотя бы одна из сумм делится на 100, то наша цель достигнута.

Допустим, что ни одно из чисел не делится на 100. Эти числа будем считать «зайцами». За клетки же примем числа 1, 2, …, 99. Сопоставим каждому числу остаток от деления его на 100. Поскольку числа на 100 не делятся, они будут давать остаток от 1 до 99, то есть каждый «заяц» попадет в какую-то «клетку». По принципу Дирихле найдутся два «зайца», попавшие в одну «клетку», то есть числа и (пусть для определенности ), дающие одинаковые остатки при делении на 100. Но тогда число делится на 100. Таким образом, сумма является искомой.

Задача №9. Дана таблица 4 4 клетки, в некоторых клетках которой расставлены звездочки. Докажите, что можно так расставить семь звездочек, что при вычеркивании любых двух столбцов и любых двух строк этой таблицы в оставшихся клетках будет всегда хотя бы одна звездочка. Докажите, что если звездочек меньше, чем семь, то всегда можно вычеркнуть две строки и два столбца, что все оставшиеся клетки будут пустыми.

Решение.

Ясно, что расположение 7 звездочек, показанное на рисунке, удовлетворяет условию задачи. Если же звездочек 6 или меньше, то найдутся два столбца, в каждом из которых стоит не более одной звездочки (принцип Дирихле). Вычеркнем оставшиеся два столбца. После этого останется не больше двух звездочек, которые можно вычеркнуть вместе со строками, в которых они стоят.

Выводы.

Таким образом, применяя данный метод, надо:

1. определить, что удобно в задаче принять за «клетки», а что за «зайцев»;
2. получить «клетки». Чаще всего «клеток» меньше (боль­ше), чем «зайцев» на одну;
3. выбрать для решения требуемую формулировку принципа Дирихле.

Задачи для самостоятельного решения.

1. В лесу растет миллион ёлок. Известно, что на каждой из них не более 600 000 иголок. Докажите, что в лесу найдутся две ёлки с одинаковым количеством иголок.
2. В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начина­ются с одной буквы?
3. На дискотеку в студенческое общежитие, в котором 42 комнаты, пришли 36 гостей. Докажите, что найдется ком­ната, в которую не пришел ни один гость.
4. В мешке лежат 10 белых и 10 черных шаров. Они тща­тельно перемешаны и неразличимы на ощупь. Какое наи­меньшее число шаров нужно вынуть из мешка вслепую, чтобы среди них наверняка оказались два шара: 1) одного цвета, 2) разного цвета, 3) белого цвета?