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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
9 клеток содержат 7 голубей, по принципу Дирихле хотя бы одна клетка не содержит голубей
9 клеток содержат 10 голубей, по принципу Дирихле хотя бы в одной клетке находятся более одного голубя

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

Принцип Дирихле нередко применяется при доказательстве теорем, особенно в дискретной математике; в частности, в теории диофантовых приближений при анализе систем линейных неравенств.

Формулировки[править | править вики-текст]

Наиболее распространена следующая формулировка этого принципа:

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

Более общая формулировка звучит так:

Если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее \left\lceil\frac{m}{n}\right\rceil кроликов, а также хотя бы в одной клетке находится не более \left\lfloor\frac{m}{n}\right\rfloor кроликов.

Возможны также несколько формулировок для частных случаев:

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

Пусть задана функция f: A \rightarrow B на конечных множествах A и B, причём |A| > n|B|, где n \in \mathbb N. Тогда некоторое своё значение функция f примет по крайней мере n+1 раз.

Примеры применения[править | править вики-текст]

Единичный квадрат, разделённый на 4 части

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

Доказательство. Теорема на первый взгляд кажется сложной и неочевидной, но с помощью принципа Дирихле доказывается без труда[1]. Разделим квадрат на 4 четверти, как показано на рисунке. По крайней мере две из пяти выбранных точек попадут в одну четверть, а тогда расстояние между ними будет меньше, чем диагональ четверти, равная \frac{\sqrt{2}}{2}. Конец доказательства.

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

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

a;\ 2a;\  3a;\  4a;\  \dots (N+1)a

Обозначим p_1 \dots p_{N+1} целые части элементов этого набора. Каждое p_k отличается от соответствующего ka менее чем на 1. Далее все числа от 0 до 1 распределим в N ящиков: в первый ящик попадут числа от 0 до 1/N, во второй — от 1/N до 2/N, и т. д.. Разницы ka-p_k тоже попадут в эти ящики, но поскольку их больше, чем число ящиков, то по принципу Дирихле в одном из ящиков будут не менее двух разниц: (ia-p_i) и (ja-p_j) (i<j). Значения разниц по построению отличаются менее чем на 1/N. Обозначим q=j-i, p=p_j-p_i, тогда предыдущую фразу можно записать в виде формулы:

|qa-p|<{1 \over N}, или: \left|a-{p\over q}\right|<\frac{1}{qN}<\frac{1}{q^2} (поскольку q<N)

В силу произвольности числа N близость дроби к числу a можно сделать как угодно малой, поэтому количество дробей {p \over q} бесконечно. Конец доказательства.

Дополнительные примеры см. в статье Китайская теорема об остатках.

Обобщение[править | править вики-текст]

Существует обобщение данного принципа на случай бесконечных множеств: не существует инъекции более мощного множества в менее мощное. Пример: если несчётное множество голубей содержится в счётном множестве ящиков, тогда хотя бы в одном из ящиков содержится несчётное множество голубей.

Литература[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Руэ, Хуанхо. Вечный странник // Искусство подсчёта. Комбинаторика и перечисление (глава 3). — М.: Де Агостини, 2014. — С. 87. — 144 с. — (Мир математики: в 45 томах, том 34). — ISBN 978-5-9774-0729-8.
  2. Дуран, Антонио. Поэзия чисел. Прекрасное и математика. — М.: Де Агостини, 2014. — С. 57. — 160 с. — (Мир математики: в 45 томах, том 27). — ISBN 978-5-9774-0722-9.