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

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

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

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

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

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

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

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

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

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

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

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

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

Квадрат со стороной 1 (единичный квадрат), разделённый на 4 части

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

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

Теорема 2. Часть компании из людей обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатий[4].

Доказательство. Пусть , , , «ящиков». Занесём в ящик тех участников компании, которые совершили рукопожатий. Если ящик не пуст, то один или более участников компании не совершили ни одного рукопожатия, а, значит, ящик тогда пуст, потому что число совершивших рукопожатия получается тогда меньше Отсюда следует, что непустых ящиков всегда меньше, чем и, следовательно, по крайней мере один ящик соответствует двум или более людям.

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература[править | править код]

Ссылки[править | править код]