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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
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 кроликов.

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

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

Обобщение[править | править исходный текст]

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

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

Литература[править | править исходный текст]