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

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

9 клеток содержат 10 голубей, по принципу Дирихле хотя бы в одной клетке находятся более одного голубя

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

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

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

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

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

Более общая формулировка звучит так(при m>n):

Если 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 раз.