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

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

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

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

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

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

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

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

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

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

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

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

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

• При любом распределении ${\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}}.}$

Доказательство. Теорема на первый взгляд кажется сложной и неочевидной, но с помощью принципа Дирихле доказывается без труда^[9]. Разделим квадрат на 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}}}}$ (это одна из версий теоремы Дирихле о диофантовых приближениях)^[10][11].

Доказательство. Для произвольного натурального числа ${\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}},}$ соответствующих всё более близким приближениям, бесконечно. ■

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

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

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

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

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

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

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

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

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

Следствия^[17].

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

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

Примеры^[18].

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

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

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

Вероятностный принцип Дирихле. Предположим что в ${\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.
• Бугаенко В. О. Математический кружок. 9 класс. Занятие №2. Принцип Дирихле  (неопр.). Дата обращения: 18 ноября 2020.

Эта страница в последний раз была отредактирована 21 марта 2024 в 08:31.