Принцип Дирихле (комбинаторика) | это... Что такое Принцип Дирихле (комбинаторика)? (original) (raw)

У этого термина существуют и другие значения, см. Принцип Дирихле.

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

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

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

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

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

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

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

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

Если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее $\left\lceil\frac{m}{n}\right\rceil$ кроликов, а также хотя бы в одной клетке находится не более $\left\lfloor\frac{m}{n}\right\rfloor$ кроликов.

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

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

Обобщение

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

Литература

Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 2.