Открыть главное меню

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

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

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

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

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

ФормулировкиПравить

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

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

Варианты более общих формулировок[1]:

  • При любом распределении   или более предметов по   ящикам в каком-нибудь ящике окажется не менее чем   предмет.
  • Если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее   кроликов, а также хотя бы в одной клетке находится не более   кроликов. Здесь уголки Айверсона   и   округляют заключённое в них выражение до целого, соответственно в бо́льшую и меньшую сторону.

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

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

Пусть задана функция   на конечных множествах A и B, причём  , где  . Тогда некоторое своё значение функция   примет по крайней мере n+1 раз.

ДоказательствоПравить

Принцип Дирихле можно доказать методом от противного. Пусть имеется N клеток и (N+1) кролик. Предположим, что в каждой клетке не более одного кролика.

 ,
 ,
...
 .

Тогда общее число кроликов  . Мы получили противоречие.

Примеры примененияПравить

 
Единичный квадрат, разделённый на 4 части

Теорема 1. При любом выборе пяти точек внутри единичного квадрата найдётся пара точек, удалённых одна от другой менее чем на  

Доказательство. Теорема на первый взгляд кажется сложной и не очевидной, но с помощью принципа Дирихле доказывается без труда[2]. Разделим квадрат на 4 четверти, как показано на рисунке. По крайней мере две из пяти выбранных точек попадут в одну четверть, а тогда расстояние между ними будет меньше, чем диагональ четверти, равная   Конец доказательства.

Теорема 2. Для любого положительного иррационального числа   существует бесконечно много дробей  , отличающихся от   менее, чем на   (это одна из версий теоремы Дирихле о диофантовых приближениях)[3] [4].

Доказательство. Для произвольного натурального числа   составим набор из  значения:

 , где  обозначает целую часть числа.

Все эти числа принадлежат интервалу от 0 до 1. Распределим их в   ящиков: в первый ящик поместим числа от 0 до   во второй — от   до   и т. д. Но поскольку этих чисел больше, чем число ящиков, то по принципу Дирихле в одном из ящиков будет не менее двух разностей:   и  

Значения разностей по построению отличаются менее чем на   Полагая   получим:

  или:   (поскольку  )

В силу произвольности числа   близость дроби к числу   можно сделать сколь угодно малой, поэтому количество дробей   бесконечно. Конец доказательства.

Дополнительные примеры можно найти в следующих источниках.

ОбобщенияПравить

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

Ряд современных обобщений принципа Дирихле приведены в статье Теория Рамсея.

ЛитератураПравить

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

  1. Алфутова Н. Б, Устинов А. В., 2009, с. 17.
  2. Руэ, Хуанхо. Вечный странник // Искусство подсчёта. Комбинаторика и перечисление (глава 3). — М.: Де Агостини, 2014. — С. 87. — 144 с. — (Мир математики: в 45 томах, том 34). — ISBN 978-5-9774-0729-8.
  3. Дуран, Антонио. Поэзия чисел. Прекрасное и математика. — М.: Де Агостини, 2014. — С. 57. — 160 с. — (Мир математики: в 45 томах, том 27). — ISBN 978-5-9774-0722-9.
  4. Алфутова Н. Б, Устинов А. В., 2009, с. 19.
  5. Алфутова Н. Б, Устинов А. В., 2009, с. 17—20.
  6. Айгнер, Циглер, 2006.