Принцип Дирихле
Материал из Википедии — свободной энциклопедии
При́нцип Дирихле́ — утверждение, устанавливающее связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий.
[править] Формулировки
Наиболее распространена следующая формулировка этого принципа:
Если в число кроликов больше, чем число клеток, то хотя бы в одной из клеток будет больше одного кролика.
Наиболее общая формулировка звучит так:
Пусть у нас имеется m кроликов и n клеток, тогда если m > n, то хотя бы в одной клетке содержится не менее n:m кроликов.
Возможны также несколько формулировок для частных случаев:
Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста.
[править] Примечания
Принцип Дирихле известен также как принцип голубей и ящиков, когда объектами являются голуби, а контейнерами — ящики. Это название распространено в английском и некоторых других языках.