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

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

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

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

В английском и некоторых других языках утверждение известно как «принцип голубей и ящиков» (англ. 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.

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

  • Айгнер М., Циглер Г. Принцип Дирихле и двойной счёт ()глава 22) // Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней. — М.: Мир, 2006. — 256 с. — ISBN 5-03-003690.
  • Алфутова Н. Б, Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. — 3-е изд., испр. доп.. — М.: МЦНМО, 2009. — 336 с. — ISBN 978-5-94057-550-4.
  • Глибичук А. А., Дайняк А. Б., Ильинский Д. Г., Купавский А. Б., Райгородский А. М., Скопенков А. Б., Чернов А. А. Элементы дискретной математики в задачах. — М.: МЦНМО, 2016. — С. 12—14. — 174 с. — ISBN 978-5-4439-3024-4.
  • Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 2. — С. 182.
  • Знак Е. И. Разбиения целочисленных решёток и принцип Дирихле // Математическое просвещение. — 2015. — Вып. 19 (третья серия). — С. 241—248.

СсылкиПравить