В статье вы познакомитесь с принципом, названным в честь немецкого математика Дирихле.

Полное имя Дирихле слишком длинное и труднозапоминаемое – Иоганн Петер Густав Лежен Дирихле, поэтому он всюду именуется просто по фамилии. Дирихле принадлежит ряд крупных открытий в самых разных областях математики, механики и математической физики, но мы рассмотрим лишь один результат, названный принципом Дирихле.

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

Обобщённый принцип Дирихле формулируется по-разному, например, так:

«При любом распределении nk+1 или более предметов по n ящикам в каком-либо ящике окажется не менее, чем k+1 предмет».

Можно формулировать обобщенный принцип Дирихле и так:

«При любом распределении m предметов в n ящиках в каком-то ящике окажется не более, чем m/n, а в каком-то – не менее, чем m/n предметов».

Это означает, что если m/n не является целым числом, то найдётся ящик, содержащий не более, чем m/n, округлённое до целого в меньшую сторону и другой ящик, содержащий не менее предметов, чем m/n, округлённое в большую сторону. Например, если m=18, n=5, то m/n=3.6, то найдётся ящик, содержащий не более трёх предметов, и другой ящик, содержащий не менее четырёх.

Рассмотрим ряд простых примеров применения принципа Дирихле.

Пусть в некотором месяце 22 рабочих дня, на кафедре работает 7 преподавателей. Каждый день кто-либо должен дежурить после занятий. Тогда кому-то из преподавателей придётся дежурить не менее четырех раз.

Среди 13 человек всегда найдется два, родившиеся в один месяц, среди 8 – в один день недели.

Если в тёмном ящике шкафа разбросаны четыре пары носок различных цветов, то среди выбранных не глядя пяти носков всегда найдётся пара одного цвета.

Рассмотрим ряд задач, где принцип Дирихле не лежит на поверхности, как в рассмотренных простых примерах, но является ключевым принципом решения. В каждой из задач нужно ещё провести подготовительную работу и догадаться, какие объекты нужно сопоставлять с кроликами, а какие – с клетками. Темы задач разные – это и арифметика, и геометрия, и комбинаторика, но их объединяет то, что в их решении задействован принцип Дирихле.

1. В прямоугольную таблицу 3×3 вписаны числа 1,2,3. Доказать, что какие-либо две суммы чисел по вертикали, горизонтали и диагонали совпадут.

Решение: всего есть 8 сумм – по трём вертикалям, трём горизонталям и двум диагоналям. Минимальное значение суммы равно 1+1+1=3, а максимальное – 3+3+3=9, значит, существует 7 вариантов значений сумм. Следовательно, какие-то две из восьми сумм совпадут.

2. На заводе работает 25 инженеров. Известно, что среди любых трёх из них есть двое знакомых друг с другом. Доказать, что найдётся инженер, у которого не менее 12 знакомых.

Решение:

Выберем любых двух инженеров, которые не знакомы между собой. Если таких нет, то все знакомы между собой ,значит, у каждого есть 24 знакомых, и задача решена.

Из оставшихся 23 инженеров каждый знаком с одним из этих двух, иначе мы имели бы тройку, среди которых не было бы знакомых. Тогда у одного из выбранных двух человек не менее 12 знакомых (23 кролика рассажены в двух клетках).

3. Дано 8 различных натуральных чисел, не больших 15. Доказать, что среди значений модулей попарных разностей есть три одинаковых.

Решение:

Кроликами в данной задаче будут служить все возможные пары чисел, а клетками – возможные значения модуля разности между числами, входящими в пару. Из 8 чисел можно образовать 8·7/2 пар, а поскольку все числа разные, и к тому же наименьшее не меньше 1, а наибольшее не превосходит 15, то модули разности могут принимать значения от 1 до 14. Таким образом, имеем 28 кроликов и 14 клеток. Но в таком случае кролики могут сидеть по два в каждой клетке, и, таким образом, не обязательно найдётся клетка, в которой сидят не менее трёх кроликов. Что же делать? Заметим, что значение модуля разности 14 можно получить единственным образом, а именно 15-1. Таким образом, в одной клетке сидит один кролик, тогда в оставшихся 13 клетках сидят 27 кроликов. Тогда по принципу Дирихле получается, что есть клетка с не менее, чем тремя кроликами, что и требовалось доказать.

4. Пусть груз упакован в ящики с весами 370 кг, 372 кг, ..., 466 кг, 468 кг. Можно ли вывезти все ящики в семь ходок, если грузоподъёмность машины составляет 3 тонны?

Решение:

Количество ящиков равно (468–370)/2+1=50, а их суммарный вес равен (468+370)/2·50=20950 кг. Трёхтонная машина за 7 ходок может перевезти 21000 кг. Однако, груз не удастся перевезти, поскольку ящики неделимые (т.е. каждый ящик или перевозится целиком, или не перевозится). Если 50 ящиков перевозится за 7 ходок, то, согласно принципу Дирихле, в одну из ходок перевозится не менее 8 ящиков. Вычислим суммарный вес восьми самых лёгких ящиков: 370+372+…+384=(370+384)/2·8=3016 кг, что превосходит грузоподъёмность машины. Следовательно, семи ходок для вывоза груза недостаточно.

5. Доказать, что правильный треугольник нельзя покрыть двумя меньшими правильными треугольниками.

Решение:

Каждый из меньших правильных треугольников не может накрывать более одной вершины большего треугольника.

6. В правильном треугольнике со стороной 3 см. выбрано 10 произвольных точек. Доказать, что найдётся пара точек, расстояние между которыми не более, чем 1 см.

Решение:

Разделим все стороны треугольника точками на три равные части и через полученные точки проведём линии, параллельные сторонам. В результате получим 9 треугольников со стороной 1 см. Таким образом, имеем 10 точек и 9 треугольников, значит, какие-то две точки принадлежат одному треугольнику со стороной 1 см. Воспользуемся леммой, которая утверждает, что длина отрезка, соединяющего любые точки треугольника, не превосходит длины его наибольшей стороны. Поскольку в данном случае имеем правильный треугольник со стороной 1 см, то расстояние между любыми двумя точками, принадлежащими ему, не превосходит 1 см.

7. Доказать, что среди чисел, состоящих только из семёрок (т.е. 7, 77, 777,....) найдётся число, которое делится на 2021.

Решение:

Рассмотрим ряд чисел 7, 77,..., 7...7 (2022 семёрки). Каждому из чисел поставим в соответствие остаток от деления этого числа на 2021. По принципу Дирихле найдётся два числа, у которых данные остатки равны между собой. Рассмотрим модуль разности этих чисел. Поскольку одно из чисел содержит большее количество семерок, другое – меньшее, то их разность будет иметь вид: 7...70...0 (некоторое количество семёрок и некоторое количество нулей). Поскольку вычитаемое и отнимаемое давали одинаковые остатки от деления на 2021, то их разность будет делиться на 2021. Поскольку 2021 не делится ни на 2, ни на 5, то в полученной разности можно сократить все нули, и при этом полученное число, состоящее из всех семёрок, будет делиться на 2021.

8. Какое наибольшее количество а) ладей б) королей может стоять на шахматной доске так, чтобы они не били друг друга?

Решение:

a) Если поставить 8 ладей на любой из диагоналей доски, то они не будут бить друг друга. Разместить 9 ладей не удастся, поскольку тогда 2 какие-либо ладьи окажутся на одной из 8 горизонталей, следовательно, они будут бить друг друга. Ответ: 8.

б) Разделим доску на 16 квадратов 2×2 и поставим королей в одну и ту же часть каждого квадрата, например, в левую верхнюю. Очевидно, так короли не бьют друг друга. Если же разместить 17 королей, то какие-то два окажутся одновременно в одном из этих 16 квадратов 2×2 и, следовательно, будут бить друг друга. Ответ: 16.

9. Квадратная доска 6×6 покрыта прямоугольными фишками 1×2 произвольным образом. Доказать, что можно провести вертикальный или горизонтальный разрез доски, не пересекающий ни одной из фишек.

Решение:

Можно провести 5 вертикальных и 5 горизонтальных разрезов доски – всего 10. Каждый разрез пересекает чётное количество фишек, т.е. или ни одной, или не менее двух. На 18 фишек приходится 10 разрезов, значит, существует разрез, не пересекающий ни одной фишки.

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

Решение:

Ковер 1 м × 1 м можно полностью покрыть 25 заплатами 20 см × 20 см. Здесь кролики – это дырки, а клетки – это заплаты. Таким образом, 51 кролик находится в 25 клетках, значит, в какой-то клетке находится не менее трёх кроликов.

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

Решение.

У каждой вершины куба сходится три грани, являющиеся попарно соседними. В данном случае кролики – это грани, клетки – их цвета. Имеем три кролика и две клетки, значит, в одной из клеток находится не менее двух кроликов.

12. Доказать, что в произвольном многограннике всегда найдётся или три пары, или тройка граней с одинаковым количеством вершин.

Решение:

В многограннике выберем грань с максимальным количеством вершин (если таких граней несколько, выберем произвольную). Обозначим это количество через n, тогда у данной грани есть n соседних граней. Таким образом, в многограннике есть не менее, чем n+1 граней, при этом минимальное количество вершин на каждой из граней – 3, максимальное – n, всего n–3+1=n–2 возможных вариантов. Здесь грани являются кроликами, а вершины – клетками, кроликов на 3 больше, чем клеток, таким образом, найдётся или клетка с не менее, чем с тремя кроликами, или три клетки с не менее, чем с двумя.

13. Пусть за круглым столом сидят представители n стран, напротив каждого стоит флажок. Но секретарь протокола все перепутал, и напротив каждого представителя оказался флажок не его страны. Доказать, что стол можно повернуть так, что флажки своей страны окажутся напротив по крайней мере двух представителей.

Решение:

Пусть клетки соответствуют положениям стола, а кролики – количеству «правильных» флажков при положении стола. За полный поворот каждый флажок по одному разу будет находиться напротив своего представителя. Таким образом, в n клетках сидит n кроликов. Однако, согласно условию задачи, в начальном положении совпадений не было, таким образом, одна клетка будет пустой, следовательно, в какой-либо другой из n-1 клеток будет не менее двух кроликов.

14. На столе лежат рядом две стопки фишек. В каждой стопке находится по 26 белых и 6 красных фишек. Стопки сложены произвольно, но одинаковым образом, т.е. белые и красные фишки находятся друг напротив друга. В одной из стопок меняют порядок фишек таким образом: снимают некоторое количество фишек, ставят на стол, и наверх ставят оставшуюся часть стопки. Доказать, что всегда можно изменить порядок фишек в одной из стопок так, чтобы никакие пары красных фишек из разных стопок не находились друг напротив друга.

Решение:

Всего в каждой из стопок находится 26+6=32 фишки. Порядок фишек в одной из стопок можно изменить 31 способом, сняв сверху от 1 до 31 фишки. Пронумеруем красные фишки в стопках сверху вниз. Тогда в начальном положении красные фишки с одинаковыми номерами находятся друг напротив друга, т.е. 1 – напротив 1, и т.д., 6 – напротив 6. Тогда после любого изменения порядка фишек никакая пара фишек с одинаковыми номерами уже не будет друг напротив друга. Однако, может случиться так, что совпадут фишки с разными номерами, например 1-2, 1-3,...,1-6; 2-1, 2-3,.., 2-6;...; 6-1,....6-5 и всего будет 5·6=30 таких пар. Но существует 31 способ изменения порядка фишек, значит, при каком-то из способов ни одна из пар фишек не совпадёт.

С.И. Доценко, О.Н. Супрун, кандидаты физ.-мат. наук, доценты факультета информационных технологий КНУ имени Тараса Шевченко