Принцип Дирихле (комбинаторика)
При́нцип Дирихле́ — простой, интуитивно понятный и часто полезный метод для доказательства утверждений о конечном множестве. Этот принцип часто используется в дискретной математике, где устанавливает связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий[1]. В английском и некоторых других языках данное утверждение известно как «принцип голубей и ящиков» (англ. pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики[2].
Наиболее распространена простейшая формулировка принципа Дирихле[3]:
Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.
Распространена также и парная к ней формулировка:
Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста.
Другие, более общие формулировки см. ниже
.Первую формулировку данного принципа историки обнаружили в популярном сборнике «Занимательная математика» (фр. Récréations Mathématiques, 1624 год, под именем H. van Etten), который опубликовал (предположительно) французский математик Жан Лёрешон[англ.][4]. Широкое распространение этот принцип получил после его применения Дирихле (начиная с 1834 года) в области теории чисел[5].
Принцип Дирихле в том или ином виде успешно применяется при доказательстве теорем, делая эти доказательства проще и понятнее. Среди его областей применения — дискретная математика, теория диофантовых приближений, анализ разрешимости систем линейных неравенств и т. п.[6] Доказательства, использующие принцип Дирихле, относятся к числу неконструктивных, поскольку они носят косвенный характер, не позволяют сделать конкретные выводы о фактическом размещении объектов[3].
Другие формулировки
Принцип Дирихле в простейшей формулировке: «если число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика» можно доказать методом «от противного». Пусть имеется [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]. Получили противоречие, ■.
Аналогично доказывается и парное утверждение: «если число клеток больше, чем число кроликов, то как минимум одна клетка пуста».
Кроме приведённых выше двух формулировок, бывают полезными ещё две, также легко доказываемые[7]:
- Если [math]\displaystyle{ n }[/math] кроликов рассажены в [math]\displaystyle{ n }[/math] клеток, причём пустых клеток нет, то в каждой клетке находится ровно один кролик.
- Если [math]\displaystyle{ n }[/math] кроликов рассажены в [math]\displaystyle{ n }[/math] клеток, причём ни одна клетка не содержит более одного кролика, то в каждой клетке находится ровно один кролик.
Варианты более общих формулировок[8]:
- При любом распределении [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. При любом выборе пяти точек внутри единичного квадрата найдётся пара точек, удалённых одна от другой не более чем на [math]\displaystyle{ \frac{\sqrt{2}}{2}. }[/math]
Доказательство. Теорема на первый взгляд кажется сложной и неочевидной, но с помощью принципа Дирихле доказывается без труда[9]. Разделим квадрат на 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] обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатий[10].
Доказательство. Пусть [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] (это одна из версий теоремы Дирихле о диофантовых приближениях)[11][12].
Доказательство. Для произвольного натурального числа [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] соответствующих всё более близким приближениям, бесконечно. ■
Дополнительные примеры можно найти в следующих источниках.
- Статья Китайская теорема об остатках.
- Книга Н. Б. Алфутовой и А. В. Устинова[13].
- Книга М. Айгнера М. и Г. Циглера[14].
- Книга А. А. Андреева и др.[15]
Геометрические применения
В геометрии используются несколько вариантов принципа Дирихле, относящихся к длинам, площадям и объёмам[16].
|
Аналогичные утверждения можно сформулировать для объёмов.
Пример[17]. В круг диаметра 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], — искомая, она пересекает все эти девять кругов. ■
Вариации и обобщения
Один из путей к обобщению принципа Дирихле распространяет его на вещественные числа[18].
Если [math]\displaystyle{ m }[/math] кроликов съели [math]\displaystyle{ n }[/math] кг травы, то по крайней мере один кролик съел не меньше [math]\displaystyle{ n \over m }[/math] кг травы. |
Следствия[18].
- Если сумма [math]\displaystyle{ n }[/math] чисел больше [math]\displaystyle{ S }[/math], то по крайней мере одно из этих чисел больше [math]\displaystyle{ \frac {S}{n}. }[/math]
- Если среднее арифметическое нескольких чисел больше [math]\displaystyle{ A }[/math], то по крайней мере одно из этих чисел больше [math]\displaystyle{ A. }[/math]
Существует обобщение принципа Дирихле на случай бесконечных множеств: не существует инъекции более мощного множества в менее мощное[19].
Примеры[19].
- Если бесконечное множество голубей содержится в конечном множестве клеток, то хотя бы в одной клетке будет более одного голубя. Более того, легко показать, что по крайней мере в одной клетке будет бесконечное множество голубей.
- Если несчётное множество голубей содержится в счётном множестве ящиков, тогда хотя бы в одной клетке будет более одного голубя. Более того, можно показать, что по крайней мере в одной клетке будет несчётное количество голубей.
На приведённое выше обобщение опирается, например, доказательство леммы Зигеля[англ.], предложенное Акселем Туэ[20].
Ряд современных обобщений принципа Дирихле приведён в статье Теория Рамсея.
- Вероятностный принцип Дирихле. Предположим что в [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].
Примечания
- ↑ Андреев и др., 1997, с. 3.
- ↑ В немецком утверждение называется «принципом ящиков» (нем. schubfachprinzip)
- ↑ 3,0 3,1 Успенский, В. А. Предисловие к математике [сборник статей]. — СПб.: ООО "Торгово-издательский дом Амфора", 2015. — С. 336—338. — 474 с. — (Популярная наука, вып. 12). — ISBN 978-5-367-03606-0.
- ↑ (2014) «The pigeonhole principle, two centuries before Dirichlet». The Mathematical Intelligencer 36 (2): 27—29. doi:10.1007/s00283-013-9389-1.
- ↑ Jeff Miller, Peter Flor, Gunnar Berg, Julio González Cabillón. Pigeonhole principle Архивная копия от 12 февраля 2010 на Wayback Machine // Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics Архивная копия от 4 марта 2009 на Wayback Machine. Electronic document, retrieved November 11, 2006
- ↑ Мат.энциклопедия, 1982.
- ↑ Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice Hall, с. 70, ISBN 978-0-13-602040-0
- ↑ Алфутова Н. Б, Устинов А. В., 2009, с. 17.
- ↑ Руэ, Хуанхо. Вечный странник // Искусство подсчёта. Комбинаторика и перечисление (глава 3). — М.: Де Агостини, 2014. — С. 87. — 144 с. — (Мир математики: в 45 томах, том 34). — ISBN 978-5-9774-0729-8.
- ↑ foxford.
- ↑ Дуран, Антонио. Поэзия чисел. Прекрасное и математика. — М.: Де Агостини, 2014. — С. 57. — 160 с. — (Мир математики: в 45 томах, том 27). — ISBN 978-5-9774-0722-9.
- ↑ Алфутова Н. Б, Устинов А. В., 2009, с. 19.
- ↑ Алфутова Н. Б, Устинов А. В., 2009, с. 17—20.
- ↑ Айгнер, Циглер, 2006.
- ↑ Андреев и др., 1997.
- ↑ Андреев и др., 1997, с. 13—16.
- ↑ Андреев и др., 1997, с. 14.
- ↑ 18,0 18,1 Андреев и др., 1997, с. 16—18.
- ↑ 19,0 19,1 Francis Su. Pigeonhole Principle . Дата обращения: 3 октября 2021. Архивировано 3 октября 2021 года.
- ↑ Thue, A. (1909), Über Annäherungswerte algebraischer Zahlen, Journal für die reine und angewandte Mathematik Т. 1909 (135): 284–305, ISSN 0075-4102, doi:10.1515/crll.1909.135.284, <http://resolver.sub.uni-goettingen.de/purl?PPN243919689_0135> Архивная копия от 30 октября 2020 на Wayback Machine
Литература
- Айгнер М., Циглер Г. Принцип Дирихле и двойной счёт ()глава 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.