- Принцип Дирихле (комбинаторика)
-
В комбинаторике при́нцип Дирихле́ (нем. Schubfachprinzip, «принцип ящиков») — утверждение, сформулированное немецким математиком Дирихле в 1834 году, устанавливающее связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках утверждение известно как «принцип голубей и ящиков» (англ. Pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики.
Принцип Дирихле применяется, в частности, в теории диофантовых приближений при анализе систем линейных неравенств.
Формулировки
- Наиболее распространена следующая формулировка этого принципа:
Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.
- Более общая формулировка звучит так:
Если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее
кроликов, а также хотя бы в одной клетке находится не более
кроликов.
- Возможны также несколько формулировок для частных случаев:
Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста.
- Пусть задана функция
на конечных множествах A и B, причём
, где
. Тогда некоторое своё значение функция
примет по крайней мере n+1 раз.
Обобщение
Существует обобщение данного принципа на случай бесконечных множеств: не существует инъекции более мощного множества в менее мощное.
Литература
- Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 2.
Категория:- Комбинаторика
Wikimedia Foundation. 2010.