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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Следствия .

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

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

Примеры .

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

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

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

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

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

Если ${\displaystyle m\cdot n<k^{1-\varepsilon }}$ для некоторого фиксированного ${\displaystyle \varepsilon >0}$ , то ${\displaystyle p(m,n,k)\to 0}$ при ${\displaystyle 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.
• Бугаенко В. О. (неопр.) . Дата обращения: 18 ноября 2020.
• (неопр.) . Дата обращения: 30 марта 2020.