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

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

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

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

Наиболее распространена простейшая формулировка принципа Дирихле: Шаблон:Начало цитаты Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика. Шаблон:Конец цитаты Распространена также и парная к ней формулировка: Шаблон:Начало цитаты Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста. Шаблон:Конец цитаты Другие, более общие формулировки см. нижеШаблон:Переход.

Первую формулировку данного принципа историки обнаружили в популярном сборнике «Занимательная математика» (Шаблон:Lang-fr, 1624 год, под именем H. van Etten), который опубликовал (предположительно) французский математик Шаблон:Iw. Широкое распространение этот принцип получил после его применения Дирихле (начиная с 1834 года) в области теории чисел.

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

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

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

1. Если $n$ кроликов рассажены в $n$ клеток, причём пустых клеток нет, то в каждой клетке находится ровно один кролик.
2. Если $n$ кроликов рассажены в $n$ клеток, причём ни одна клетка не содержит более одного кролика, то в каждой клетке находится ровно один кролик.

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

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

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

К теореме 1

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

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

Теорема 2. Часть компании из $N$ людей $(N>1)$ обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатий.

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

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

Доказательство. Для произвольного натурального числа $N$ составим набор из $(N+1)$ значения:

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

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

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

$|q\cdot a-p|<\frac{1}{N},$ или: $|a-\frac{p}{q}|<\frac{1}{q\cdot N}⩽\frac{1}{q^2}$ (поскольку $q⩽N$).

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

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

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

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

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

1. Если на отрезке длины $L$ расположено несколько отрезков с суммой длин больше $L$, то по меньшей мере два из этих отрезков имеют общую точку.
2. Обобщение. Если на отрезке длины $L$ расположено несколько отрезков, сумма длин которых больше $kL$, то по крайней мере одна точка покрыта не менее чем $k+1$ из этих отрезков.
3. Если сумма длин отрезков меньше $L$, то ими нельзя полностью покрыть отрезок длины $L$.
4. Если внутри фигуры площади $S$ находится несколько фигур, имеющих сумму площадей больше $S$, то по меньшей мере две из них имеют общую точку.
5. Если сумма площадей нескольких фигур меньше $S$, то ими нельзя покрыть фигуру площади $S$.
   

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

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

Доказательство. Пусть $D$ — произвольный диаметр исходного круга (длины 6). Спроектируем все внутренние круги на диаметр $D$. Сумма длин проекций, очевидно, равна сумме диаметров кругов, то есть 50, и они покрывают (не обязательно полностью) диаметр $D$. Поскольку $50>8\cdot D$, то согласно 2-му варианту принципа Дирихле на отрезке АВ есть точка, принадлежащая проекциям по крайней мере девяти кругов. Тогда прямая, проходящая через эту точку и перпендикулярная диаметру $D$, — искомая, она пересекает все эти девять кругов. Шаблон:ЧТД

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

Один из путей к обобщению принципа Дирихле распространяет его на вещественные числаШаблон:Sfn. Шаблон:Рамка Если $m$ кроликов съели $n$ кг травы, то по крайней мере один кролик съел не меньше $\frac{n}{m}$ кг травы. |} Следствия.

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

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

Примеры.

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

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

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

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

Если $m\cdot n>k^{1+\epsilon }$ для некоторого фиксированного $\epsilon >0$, то $p(m,n,k)\to 1$ при $k\to \mathrm{\infty }$.

Если $m\cdot n<k^{1-\epsilon }$ для некоторого фиксированного $\epsilon >0$, то $p(m,n,k)\to 0$ при $k\to \mathrm{\infty }$.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья

Ссылки

• Шаблон:Публикация
• Шаблон:Cite web