Дирихле принцип

9 клеток вмещают 7 голубей, значит, хотя бы 9-7=2 клетки свободны

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

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

Предположим, m кроликов рассажены в n клетках. Наиболее распространена следующая формулировка этого принципа:

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

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

Предположим, m кроликов рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n кроликов, а также хотя бы в одной другой клетке содержится не более m:n кроликов.

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

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

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

Примечания

Принцип Дирихле известен также как принцип голубей и ящиков, когда объектами являются голуби, а контейнерами — ящики. Это название распространено в английском и некоторых других языках.