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

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

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

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

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

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

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

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

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

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

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

Другие формулировкиПравить

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

Принцип Дирихле в простейшей формулировке: «если число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика» можно доказать методом «от противного». Пусть имеется $n$$n$  клеток и $m$$m$  кроликов, причём $m>n$$m>n$ . Обозначим.$k_i$$k_i$  число кроликов в $i$$i$ -й клетке ($i=1,2,\dots <!--\; \dots \; -->n$$i=1,2,\dots n$ ). Предположим, что в каждой клетке не более одного кролика:

• $k_1⩽<!--\; ⩽\; -->1$$k_{1}\leqslant 1$  (число кроликов в 1-й клетке меньше или равно 1);
• $k_2⩽<!--\; ⩽\; -->1$$k_{2}\leqslant 1$  (число кроликов во 2-й клетке меньше или равно 1);
• ...
• $k_n⩽<!--\; ⩽\; -->1$$k_{n}\leqslant 1$  (число кроликов в $n$$n$ -й клетке меньше или равно 1).

Тогда общее число кроликов $m=k_1+k_2+\dots <!--\; \dots \; -->+k_n⩽<!--\; ⩽\; -->1+1+\dots <!--\; \dots \; -->+1=n.$$m=k_{1}+k_{2}+\ldots +k_{n}\leqslant 1+1+\ldots +1=n.$  Следовательно $m⩽<!--\; ⩽\; -->n$$m\leqslant n$  Но по условию задачи $m>n$$m>n$ . Получили противоречие, ■.

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

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

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

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

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

Примеры примененияПравить

 

К теореме 1

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

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

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

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

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

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

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

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

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

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

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

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

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

Геометрические примененияПравить

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

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

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

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

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

Вариации и обобщенияПравить

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

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

Следствия.

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

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

Примеры.

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

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

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

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

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

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

ЛитератураПравить

• Айгнер М., Циглер Г. Принцип Дирихле и двойной счёт ()глава 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.