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

Материал из Википедии — свободной энциклопедии

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

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

[править] Формулировки

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

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

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

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

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

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

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

[править] Примечания

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

Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её.