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

У этого термина существуют и другие значения, см. Принцип Дирихле.

9 клеток содержат 7 голубей, по принципу Дирихле хотя бы одна клетка содержит не больше 7/9 голубя (т.е ноль)

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 раз.

Обобщение

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

Литература

• Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 2.