WikiSort.ru - Не сортированное

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

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

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

Формулировки

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

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

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

• При любом распределении ${\displaystyle nk+1}$ или более предметов по ${\displaystyle n}$ ящикам в каком-нибудь ящике окажется не менее чем ${\displaystyle k+1}$ предмет.
• Если m кроликов рассажены в 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\colon A\rightarrow B}$ на конечных множествах A и B, причём ${\displaystyle |A|>n|B|}$ , где ${\displaystyle n\in \mathbb {N} }$ . Тогда некоторое своё значение функция ${\displaystyle f}$ примет по крайней мере n+1 раз.

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

Принцип Дирихле можно доказать методом от противного. Пусть имеется N клеток и (N+1) кролик. Предположим, что в каждой клетке не более одного кролика.

${\displaystyle n_{1}\leqslant 1}$ ,

${\displaystyle n_{2}\leqslant 1}$ ,

...

${\displaystyle n_{N}\leqslant 1}$ .

Тогда общее число кроликов ${\displaystyle n_{1}+n_{2}+...+n_{N}\leqslant 1+1+...+1=N}$ . Мы получили противоречие.

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

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

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

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

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

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

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

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

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

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

Дополнительные примеры см. в статье Китайская теорема об остатках и в книге Н. Б. Алфутовой и А. В. Устинова^[5].

Обобщения

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

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

Литература

• Алфутова Н. Б, Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. — 3-е изд., испр. доп.. — М.: МЦНМО, 2009. — 336 с. — ISBN 978-5-94057-550-4.
• Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 2.
• Знак Е. И. Разбиения целочисленных решёток и принцип Дирихле // Математическое просвещение. — 2015. — Вып. 19 (третья серия). — С. 241—248.

Примечания