Принцип Дирихле (комбинаторика)

9 клеток содержат 10 голубей, по принципу Дирихле хотя бы в одной клетке находятся более одного голубя

9 клеток содержат 7 голубей, по принципу Дирихле хотя бы одна клетка (фактически даже больше одной) не содержит голубей

При́нцип Дирихле́ — простой, интуитивно понятный и часто полезный метод для доказательства утверждений о конечном множестве. Этот принцип часто используется в дискретной математике, где устанавливает связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках данное утверждение известно как «принцип голубей и ящиков» (англ. pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики.

Наиболее распространена простейшая формулировка принципа Дирихле:

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

Распространена также и парная к ней формулировка:

Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста.

Другие, более общие формулировки см. ниже.

Первую формулировку данного принципа историки обнаружили в популярном сборнике «Занимательная математика» (фр. Récréations Mathématiques, 1624 год, под именем H. van Etten), который опубликовал (предположительно) французский математик Жан Лёрешон. Широкое распространение этот принцип получил после его применения Дирихле (начиная с 1834 года) в области теории чисел.

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

Другие формулировки

Доказательство

Принцип Дирихле в простейшей формулировке: «если число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика» можно доказать методом «от противного». Пусть имеется [math]\displaystyle{ n }[/math] клеток и [math]\displaystyle{ m }[/math] кроликов, причём [math]\displaystyle{ m \gt n }[/math]. Обозначим.[math]\displaystyle{ k_i }[/math] число кроликов в [math]\displaystyle{ i }[/math]-й клетке ([math]\displaystyle{ i=1, 2, \dots n }[/math]). Предположим, что в каждой клетке не более одного кролика:

• [math]\displaystyle{ k_1 \leqslant 1 }[/math] (число кроликов в 1-й клетке меньше или равно 1);
• [math]\displaystyle{ k_2 \leqslant 1 }[/math] (число кроликов во 2-й клетке меньше или равно 1);
• ...
• [math]\displaystyle{ k_n \leqslant 1 }[/math] (число кроликов в [math]\displaystyle{ n }[/math]-й клетке меньше или равно 1).

Тогда общее число кроликов [math]\displaystyle{ m = k_1 + k_2 + \ldots + k_n \leqslant 1 + 1 + \ldots + 1 = n. }[/math] Следовательно [math]\displaystyle{ m \leqslant n }[/math] Но по условию задачи [math]\displaystyle{ m \gt n }[/math]. Получили противоречие, ■.

Аналогично доказывается и парное утверждение: «если число клеток больше, чем число кроликов, то как минимум одна клетка пуста».

Кроме приведённых выше двух формулировок, бывают полезными ещё две, также легко доказываемые:

1. Если [math]\displaystyle{ n }[/math] кроликов рассажены в [math]\displaystyle{ n }[/math] клеток, причём пустых клеток нет, то в каждой клетке находится ровно один кролик.
2. Если [math]\displaystyle{ n }[/math] кроликов рассажены в [math]\displaystyle{ n }[/math] клеток, причём ни одна клетка не содержит более одного кролика, то в каждой клетке находится ровно один кролик.

Варианты более общих формулировок:

• При любом распределении [math]\displaystyle{ kn + 1 }[/math] или более предметов по [math]\displaystyle{ n }[/math] ящикам в каком-нибудь ящике окажется не менее чем [math]\displaystyle{ k + 1 }[/math] предмет.
• Если [math]\displaystyle{ m }[/math] кроликов рассажены в [math]\displaystyle{ n }[/math] клеток, то хотя бы в одной клетке находится не менее [math]\displaystyle{ \left \lceil \frac{m}{n} \right \rceil }[/math] кроликов, а также хотя бы в одной клетке находится не более [math]\displaystyle{ \left \lfloor \frac{m}{n} \right \rfloor }[/math] кроликов. Здесь уголки Айверсона [math]\displaystyle{ \lceil \dots \rceil }[/math] и [math]\displaystyle{ \lfloor \dots \rfloor }[/math] округляют заключённое в них выражение до целого, соответственно в бо́льшую и меньшую сторону.
• Пусть задана функция [math]\displaystyle{ f, }[/math] определённая на конечном множестве [math]\displaystyle{ A }[/math] и отображающая его в конечное множество [math]\displaystyle{ B }[/math]: [math]\displaystyle{ f \colon A \rightarrow B, }[/math] причём [math]\displaystyle{ \left | A \right | \gt n \cdot \left | B \right | , }[/math] где [math]\displaystyle{ n }[/math] — некоторое натуральное число, а конструкция вида [math]\displaystyle{ \left | X \right | }[/math] означает число элементов конечного множества [math]\displaystyle{ X }[/math] (мощность множества). Тогда некоторое своё значение функция [math]\displaystyle{ f }[/math] примет по крайней мере [math]\displaystyle{ n+1 }[/math] раз.

Примеры применения

К теореме 1

Теорема 1. При любом выборе пяти точек внутри единичного квадрата найдётся пара точек, удалённых одна от другой не более чем на [math]\displaystyle{ \frac{\sqrt{2}}{2}. }[/math]

Доказательство. Теорема на первый взгляд кажется сложной и неочевидной, но с помощью принципа Дирихле доказывается без труда. Разделим квадрат на 4 четверти, как показано на рисунке. По принципу Дирихле, по крайней мере две из пяти выбранных точек попадут в одну четверть, а тогда расстояние между ними будет не больше, чем диагональ четверти, равная [math]\displaystyle{ \sqrt{ { \left( \frac{1}{2} \right) }^2 + { \left( \frac{1}{2} \right) }^2 } = \frac{ \sqrt{2} }{2}. }[/math] ■

Теорема 2. Часть компании из [math]\displaystyle{ N }[/math] людей [math]\displaystyle{ \left ( N \gt 1 \right ) }[/math] обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатий.

Доказательство. Пусть [math]\displaystyle{ \{H_0, H_1, \dots H_{N-1}\} }[/math] — [math]\displaystyle{ N }[/math] «ящиков». Занесём в ящик [math]\displaystyle{ H_k }[/math] тех участников компании, которые совершили [math]\displaystyle{ k }[/math] рукопожатий. Если ящик [math]\displaystyle{ H_0 }[/math] не пуст, то один или более участников компании не совершили ни одного рукопожатия, а, значит, ящик [math]\displaystyle{ H_{N-1} }[/math] тогда пуст, потому что число совершивших рукопожатия получается тогда меньше [math]\displaystyle{ N. }[/math] Отсюда следует, что непустых ящиков всегда меньше, чем [math]\displaystyle{ N, }[/math] и, следовательно, по крайней мере один ящик соответствует двум или более людям. ■

Теорема 3. Для любого положительного иррационального числа [math]\displaystyle{ a }[/math] существует бесконечно много дробей [math]\displaystyle{ \frac{p}{q}, }[/math] отличающихся от [math]\displaystyle{ a }[/math] менее, чем на [math]\displaystyle{ \frac{1}{q^2} }[/math] (это одна из версий теоремы Дирихле о диофантовых приближениях).

Доказательство. Для произвольного натурального числа [math]\displaystyle{ N }[/math] составим набор из [math]\displaystyle{ (N+1) }[/math] значения:

[math]\displaystyle{ d_1 = 1 \cdot a-[1 \cdot a], }[/math] [math]\displaystyle{ d_2 = 2 \cdot a-[2 \cdot a], }[/math] [math]\displaystyle{ d_3 = 3 \cdot a-[3 \cdot a], }[/math] [math]\displaystyle{ \dots, }[/math] [math]\displaystyle{ d_{N+1} = (N+1) \cdot a-[(N+1) \cdot a] , }[/math] где [math]\displaystyle{ [x] }[/math] обозначает целую часть числа.

Все эти числа принадлежат интервалу от 0 до 1 не включительно. Распределим их в [math]\displaystyle{ N }[/math] ящиков: в первый ящик поместим числа от 0 включительно до [math]\displaystyle{ 1/N }[/math] не включительно, во второй — от [math]\displaystyle{ 1/N }[/math] включительно до [math]\displaystyle{ 2/N }[/math] не включительно и т. д., в [math]\displaystyle{ N }[/math]-й — от [math]\displaystyle{ (N-1)/N }[/math] включительно до [math]\displaystyle{ N/N }[/math] не включительно. Но поскольку количество чисел [math]\displaystyle{ \left ( N+1 \right ) }[/math] больше, чем число ящиков [math]\displaystyle{ \left ( N \right ) , }[/math] то по принципу Дирихле в одном из ящиков будет не менее двух разностей: [math]\displaystyle{ d_i = \left ( i \cdot a-[i \cdot a] \right ) }[/math] и [math]\displaystyle{ d_j = \left ( j \cdot a-[j \cdot a] \right ) }[/math] при [math]\displaystyle{ i \lt j. }[/math]

Значения разностей по построению отличаются менее чем на [math]\displaystyle{ \frac{1}{N} : }[/math] [math]\displaystyle{ d_j - d_i \lt \frac{1}{N}. }[/math] Полагая [math]\displaystyle{ q = j-i }[/math] и [math]\displaystyle{ p = [j \cdot a] - [i \cdot a], }[/math] получим:

[math]\displaystyle{ |q \cdot a-p| \lt \frac{1}{N}, }[/math] или: [math]\displaystyle{ \left | a - \frac{p}{q} \right | \lt \frac{1}{q \cdot N} \leqslant \frac{1}{q^2} }[/math] (поскольку [math]\displaystyle{ q \leqslant N }[/math]).

В силу произвольности числа [math]\displaystyle{ N }[/math] близость дроби [math]\displaystyle{ p/q }[/math] к числу [math]\displaystyle{ a }[/math] можно сделать сколь угодно малой (при этом заведомо ненулевой, поскольку [math]\displaystyle{ a }[/math] по условию иррационально). Поэтому количество дробей [math]\displaystyle{ \frac{p}{q}, }[/math] соответствующих всё более близким приближениям, бесконечно. ■

Дополнительные примеры можно найти в следующих источниках.

• Статья Китайская теорема об остатках.
• Книга Н. Б. Алфутовой и А. В. Устинова.
• Книга М. Айгнера М. и Г. Циглера.
• Книга А. А. Андреева и др.

Геометрические применения

В геометрии используются несколько вариантов принципа Дирихле, относящихся к длинам, площадям и объёмам.

Если на отрезке длины [math]\displaystyle{ L }[/math] расположено несколько отрезков с суммой длин больше [math]\displaystyle{ L }[/math], то по меньшей мере два из этих отрезков имеют общую точку. Обобщение. Если на отрезке длины [math]\displaystyle{ L }[/math] расположено несколько отрезков, сумма длин которых больше [math]\displaystyle{ kL }[/math], то по крайней мере одна точка покрыта не менее чем [math]\displaystyle{ k + 1 }[/math] из этих отрезков. Если сумма длин отрезков меньше [math]\displaystyle{ L }[/math], то ими нельзя полностью покрыть отрезок длины [math]\displaystyle{ L }[/math]. Если внутри фигуры площади [math]\displaystyle{ S }[/math] находится несколько фигур, имеющих сумму площадей больше [math]\displaystyle{ S }[/math], то по меньшей мере две из них имеют общую точку. Если сумма площадей нескольких фигур меньше [math]\displaystyle{ S }[/math], то ими нельзя покрыть фигуру площади [math]\displaystyle{ S }[/math].

Аналогичные утверждения можно сформулировать для объёмов.

Пример. В круг диаметра 6 произвольным образом помещены несколько кругов, сумма диаметров которых равна 50. Доказать, что найдётся прямая, которая пересекает не менее девяти из этих кругов.

Доказательство. Пусть [math]\displaystyle{ D }[/math] — произвольный диаметр исходного круга (длины 6). Спроектируем все внутренние круги на диаметр [math]\displaystyle{ D }[/math]. Сумма длин проекций, очевидно, равна сумме диаметров кругов, то есть 50, и они покрывают (не обязательно полностью) диаметр [math]\displaystyle{ D }[/math]. Поскольку [math]\displaystyle{ 50 \gt 8 \cdot D }[/math], то согласно 2-му варианту принципа Дирихле на отрезке АВ есть точка, принадлежащая проекциям по крайней мере девяти кругов. Тогда прямая, проходящая через эту точку и перпендикулярная диаметру [math]\displaystyle{ D }[/math], — искомая, она пересекает все эти девять кругов. ■

Вариации и обобщения

Один из путей к обобщению принципа Дирихле распространяет его на вещественные числа.

Если [math]\displaystyle{ m }[/math] кроликов съели [math]\displaystyle{ n }[/math] кг травы, то по крайней мере один кролик съел не меньше [math]\displaystyle{ n \over m }[/math] кг травы.

Следствия.

1. Если сумма [math]\displaystyle{ n }[/math] чисел больше [math]\displaystyle{ S }[/math], то по крайней мере одно из этих чисел больше [math]\displaystyle{ \frac {S}{n}. }[/math]
2. Если среднее арифметическое нескольких чисел больше [math]\displaystyle{ A }[/math], то по крайней мере одно из этих чисел больше [math]\displaystyle{ A. }[/math]

Существует обобщение принципа Дирихле на случай бесконечных множеств: не существует инъекции более мощного множества в менее мощное.

Примеры.

• Если бесконечное множество голубей содержится в конечном множестве клеток, то хотя бы в одной клетке будет более одного голубя. Более того, легко показать, что по крайней мере в одной клетке будет бесконечное множество голубей.
• Если несчётное множество голубей содержится в счётном множестве ящиков, тогда хотя бы в одной клетке будет более одного голубя. Более того, можно показать, что по крайней мере в одной клетке будет несчётное количество голубей.

На приведённое выше обобщение опирается, например, доказательство леммы Зигеля, предложенное Акселем Туэ.

Ряд современных обобщений принципа Дирихле приведён в статье Теория Рамсея.

Вероятностный принцип Дирихле. Предположим что в [math]\displaystyle{ m }[/math] случайных клетках из [math]\displaystyle{ k }[/math] сидят кролики и в [math]\displaystyle{ n }[/math] случайных клетках из тех же [math]\displaystyle{ k }[/math] клеток сидят крольчихи. Обозначим через [math]\displaystyle{ p(m,n,k) }[/math] вероятность того, что в какой-то клетке сидит кролик с крольчихой.

Если [math]\displaystyle{ m\cdot n\gt k^{1+\varepsilon} }[/math] для некоторого фиксированного [math]\displaystyle{ \varepsilon\gt 0 }[/math], то [math]\displaystyle{ p(m,n,k)\to 1 }[/math] при [math]\displaystyle{ k\to\infty }[/math].

Если [math]\displaystyle{ m\cdot n\lt k^{1-\varepsilon} }[/math] для некоторого фиксированного [math]\displaystyle{ \varepsilon\gt 0 }[/math], то [math]\displaystyle{ p(m,n,k)\to 0 }[/math] при [math]\displaystyle{ k\to\infty }[/math].

Литература

• Айгнер М., Циглер Г. Принцип Дирихле и двойной счёт ()глава 22) // Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней. — М.: Мир, 2006. — 256 с. — ISBN 5-03-003690-3.
• Алфутова Н. Б, Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. — 3-е изд., испр. доп.. — М.: МЦНМО, 2009. — 336 с. — ISBN 978-5-94057-550-4.
• Андреев А. А., Горелов Г. Н., Люлев А. И., Савин А. Н. Принцип Дирихле. Учебное издание. — Самара: Пифагор, 1997. — 21 с. — (Серия А: Математика. Вып. 1).
• Глибичук А. А., Дайняк А. Б., Ильинский Д. Г., Купавский А. Б., Райгородский А. М., Скопенков А. Б., Чернов А. А. Элементы дискретной математики в задачах. — М.: МЦНМО, 2016. — С. 12—14. — 174 с. — ISBN 978-5-4439-3024-4.
• Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 2. — С. 182.
• Знак Е. И. Разбиения целочисленных решёток и принцип Дирихле // Математическое просвещение. — 2015. — Вып. 19 (третья серия). — С. 241—248.

Ссылки

• Болтянский В. Шесть зайцев в пяти клетках // Квант. — 1977. — № 2. — С. 17—20, 37, 42.
• Бугаенко В. О. Математический кружок. 9 класс. Занятие №2. Принцип Дирихле (неопр.). Дата обращения: 18 ноября 2020.
• Принцип Дирихле (неопр.). Дата обращения: 30 марта 2020.