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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
9 клеток содержат 7 голубей, по принципу Дирихле хотя бы одна клетка не содержит голубей
9 клеток содержат 10 голубей, по принципу Дирихле хотя бы в одной клетке находятся более одного голубя

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

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

Формулировки[править | править вики-текст]

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

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

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

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

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

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

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

Примеры применения[править | править вики-текст]

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

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

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

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

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

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

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

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

Дополнительные примеры см. в статье Китайская теорема об остатках и в книге Н. Б, Алфутовой и А. В. Устинова[5].

Обобщение[править | править вики-текст]

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

Литература[править | править вики-текст]

Примечания[править | править вики-текст]

  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.