Русская Википедия:Принцип Дирихле (комбинаторика)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Значения

Файл:TooManyPigeons.jpg
9 клеток содержат 10 голубей, по принципу Дирихле хотя бы в одной клетке находятся более одного голубя
Файл:Pigeons-in-holes.jpg
9 клеток содержат 7 голубей, по принципу Дирихле хотя бы одна клетка (фактически даже больше одной) не содержит голубей

При́нцип Дирихле́ — простой, интуитивно понятный и часто полезный метод для доказательства утверждений о конечном множестве. Этот принцип часто используется в дискретной математике, где устанавливает связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условийШаблон:Sfn. В английском и некоторых других языках данное утверждение известно как «принцип голубей и ящиков» (Шаблон:Lang-en), когда объектами являются голуби, а контейнерами — ящики[1].

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

Первую формулировку данного принципа историки обнаружили в популярном сборнике «Занимательная математика» (Шаблон:Lang-fr, 1624 год, под именем H. van Etten), который опубликовал (предположительно) французский математик Шаблон:Iw[3]. Широкое распространение этот принцип получил после его применения Дирихле (начиная с 1834 года) в области теории чисел[4].

Принцип Дирихле в том или ином виде успешно применяется при доказательстве теорем, делая эти доказательства проще и понятнее. Среди его областей применения — дискретная математика, теория диофантовых приближений, анализ разрешимости систем линейных неравенств Шаблон:ИтпШаблон:Sfn Доказательства, использующие принцип Дирихле, относятся к числу неконструктивных, поскольку они носят косвенный характер, не позволяют сделать конкретные выводы о фактическом размещении объектов[2].

Другие формулировки

Шаблон:Скрытый Кроме приведённых выше двух формулировок, бывают полезными ещё две, также легко доказываемые[5]: Шаблон:Начало цитаты

  1. Если <math>n</math> кроликов рассажены в <math>n</math> клеток, причём пустых клеток нет, то в каждой клетке находится ровно один кролик.
  2. Если <math>n</math> кроликов рассажены в <math>n</math> клеток, причём ни одна клетка не содержит более одного кролика, то в каждой клетке находится ровно один кролик.

Шаблон:Конец цитаты

Варианты более общих формулировокШаблон:Sfn:

  • При любом распределении <math>kn + 1</math> или более предметов по <math>n</math> ящикам в каком-нибудь ящике окажется не менее чем <math>k + 1</math> предмет.
  • Если <math>m</math> кроликов рассажены в <math>n</math> клеток, то хотя бы в одной клетке находится не менее <math>\left \lceil \frac{m}{n} \right \rceil</math> кроликов, а также хотя бы в одной клетке находится не более <math>\left \lfloor \frac{m}{n} \right \rfloor</math> кроликов. Здесь уголки Айверсона <math>\lceil \dots \rceil</math> и <math>\lfloor \dots \rfloor</math> округляют заключённое в них выражение до целого, соответственно в бо́льшую и меньшую сторону.
  • Пусть задана функция <math>f,</math> определённая на конечном множестве <math>A</math> и отображающая его в конечное множество <math>B</math>: <math>f \colon A \rightarrow B,</math> причём <math>\left | A \right | > n \cdot \left | B \right | , </math> где <math>n</math> — некоторое натуральное число, а конструкция вида <math>\left | X \right |</math> означает число элементов конечного множества <math>X</math> (мощность множества). Тогда некоторое своё значение функция <math>f</math> примет по крайней мере <math>n+1</math> раз.

Примеры применения

Файл:Blank Go gameboard.png
К теореме 1

Теорема 1. При любом выборе пяти точек внутри единичного квадрата найдётся пара точек, удалённых одна от другой не более чем на <math>\frac{\sqrt{2}}{2}.</math>

Доказательство. Теорема на первый взгляд кажется сложной и неочевидной, но с помощью принципа Дирихле доказывается без труда[6]. Разделим квадрат на 4 четверти, как показано на рисунке. По принципу Дирихле, по крайней мере две из пяти выбранных точек попадут в одну четверть, а тогда расстояние между ними будет не больше, чем диагональ четверти, равная <math>\sqrt{ { \left( \frac{1}{2} \right) }^2 + { \left( \frac{1}{2} \right) }^2 } = \frac{ \sqrt{2} }{2}.</math> Шаблон:ЧТД

Теорема 2. Часть компании из <math>N</math> людей <math>\left ( N > 1 \right )</math> обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатийШаблон:Sfn.

Доказательство. Пусть <math>\{H_0, H_1, \dots H_{N-1}\}</math> — <math>N</math> «ящиков». Занесём в ящик <math>H_k</math> тех участников компании, которые совершили <math>k</math> рукопожатий. Если ящик <math>H_0</math> не пуст, то один или более участников компании не совершили ни одного рукопожатия, а, значит, ящик <math>H_{N-1}</math> тогда пуст, потому что число совершивших рукопожатия получается тогда меньше <math>N.</math> Отсюда следует, что непустых ящиков всегда меньше, чем <math>N,</math> и, следовательно, по крайней мере один ящик соответствует двум или более людям. Шаблон:ЧТД

Теорема 3. Для любого положительного иррационального числа <math>a</math> существует бесконечно много дробей <math>\frac{p}{q},</math> отличающихся от <math>a</math> менее, чем на <math>\frac{1}{q^2}</math> (это одна из версий теоремы Дирихле о диофантовых приближениях)[7]Шаблон:Sfn.

Доказательство. Для произвольного натурального числа <math>N</math> составим набор из <math>(N+1)</math> значения:

<math>d_1 = 1 \cdot a-[1 \cdot a],</math> <math>d_2 = 2 \cdot a-[2 \cdot a],</math> <math>d_3 = 3 \cdot a-[3 \cdot a],</math> <math>\dots,</math> <math>d_{N+1} = (N+1) \cdot a-[(N+1) \cdot a] , </math> где <math>[x]</math> обозначает целую часть числа.

Все эти числа принадлежат интервалу от 0 до 1 не включительно. Распределим их в <math>N</math> ящиков: в первый ящик поместим числа от 0 включительно до <math>1/N</math> не включительно, во второй — от <math>1/N</math> включительно до <math>2/N</math> не включительно Шаблон:Итд, в <math>N</math>-й — от <math>(N-1)/N</math> включительно до <math>N/N</math> не включительно. Но поскольку количество чисел <math>\left ( N+1 \right ) </math> больше, чем число ящиков <math>\left ( N \right ) ,</math> то по принципу Дирихле в одном из ящиков будет не менее двух разностей: <math>d_i = \left ( i \cdot a-[i \cdot a] \right ) </math> и <math>d_j = \left ( j \cdot a-[j \cdot a] \right ) </math> при <math>i < j.</math>

Значения разностей по построению отличаются менее чем на <math>\frac{1}{N} :</math> <math>d_j - d_i < \frac{1}{N}.</math> Полагая <math>q = j-i</math> и <math>p = [j \cdot a] - [i \cdot a],</math> получим:

<math>|q \cdot a-p| < \frac{1}{N},</math> или: <math>\left | a - \frac{p}{q} \right | < \frac{1}{q \cdot N} \leqslant \frac{1}{q^2}</math> (поскольку <math>q \leqslant N</math>).

В силу произвольности числа <math>N</math> близость дроби <math>p/q</math> к числу <math>a</math> можно сделать сколь угодно малой (при этом заведомо ненулевой, поскольку <math>a</math> по условию иррационально). Поэтому количество дробей <math>\frac{p}{q},</math> соответствующих всё более близким приближениям, бесконечно. Шаблон:ЧТД

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

Геометрические применения

В геометрии используются несколько вариантов принципа Дирихле, относящихся к длинам, площадям и объёмамШаблон:Sfn. Шаблон:Рамка

  1. Если на отрезке длины <math>L</math> расположено несколько отрезков с суммой длин больше <math>L</math>, то по меньшей мере два из этих отрезков имеют общую точку.
  2. Обобщение. Если на отрезке длины <math>L</math> расположено несколько отрезков, сумма длин которых больше <math>kL</math>, то по крайней мере одна точка покрыта не менее чем <math>k + 1</math> из этих отрезков.
  3. Если сумма длин отрезков меньше <math>L</math>, то ими нельзя полностью покрыть отрезок длины <math>L</math>.
  4. Если внутри фигуры площади <math>S</math> находится несколько фигур, имеющих сумму площадей больше <math>S</math>, то по меньшей мере две из них имеют общую точку.
  5. Если сумма площадей нескольких фигур меньше <math>S</math>, то ими нельзя покрыть фигуру площади <math>S</math>.

|} Аналогичные утверждения можно сформулировать для объёмов.

ПримерШаблон:Sfn. В круг диаметра 6 произвольным образом помещены несколько кругов, сумма диаметров которых равна 50. Доказать, что найдётся прямая, которая пересекает не менее девяти из этих кругов.

Доказательство. Пусть <math>D</math> — произвольный диаметр исходного круга (длины 6). Спроектируем все внутренние круги на диаметр <math>D</math>. Сумма длин проекций, очевидно, равна сумме диаметров кругов, то есть 50, и они покрывают (не обязательно полностью) диаметр <math>D</math>. Поскольку <math>50 > 8 \cdot D</math>, то согласно 2-му варианту принципа Дирихле на отрезке АВ есть точка, принадлежащая проекциям по крайней мере девяти кругов. Тогда прямая, проходящая через эту точку и перпендикулярная диаметру <math>D</math>, — искомая, она пересекает все эти девять кругов. Шаблон:ЧТД

Вариации и обобщения

Один из путей к обобщению принципа Дирихле распространяет его на вещественные числаШаблон:Sfn. Шаблон:Рамка Если <math>m</math> кроликов съели <math>n</math> кг травы, то по крайней мере один кролик съел не меньше <math>n \over m</math> кг травы. |} Следствия[8].

  1. Если сумма <math>n</math> чисел больше <math>S</math>, то по крайней мере одно из этих чисел больше <math>\frac {S}{n}.</math>
  2. Если среднее арифметическое нескольких чисел больше <math>A</math>, то по крайней мере одно из этих чисел больше <math>A.</math>

Существует обобщение принципа Дирихле на случай бесконечных множеств: не существует инъекции более мощного множества в менее мощное[9].

Примеры[9].

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

На приведённое выше обобщение опирается, например, доказательство Шаблон:Iw, предложенное Акселем Туэ[10].

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

Вероятностный принцип Дирихле. Предположим что в <math>m</math> случайных клетках из <math>k</math> сидят кролики и в <math>n</math> случайных клетках из тех же <math>k</math> клеток сидят крольчихи. Обозначим через <math>p(m,n,k)</math> вероятность того, что в какой-то клетке сидит кролик с крольчихой.
Если <math>m\cdot n>k^{1+\varepsilon}</math> для некоторого фиксированного <math>\varepsilon>0</math>, то <math>p(m,n,k)\to 1</math> при <math>k\to\infty</math>.
Если <math>m\cdot n<k^{1-\varepsilon}</math> для некоторого фиксированного <math>\varepsilon>0</math>, то <math>p(m,n,k)\to 0</math> при <math>k\to\infty</math>.

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:ВС Шаблон:Добротная статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ В немецком утверждение называется «принципом ящиков» (Шаблон:Lang-de)
  2. ↑ 2,0 2,1 Шаблон:Книга
  3. ↑ Шаблон:Cite journal
  4. ↑ Jeff Miller, Peter Flor, Gunnar Berg, Julio González Cabillón. Pigeonhole principle Шаблон:Wayback // Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics Шаблон:Wayback. Electronic document, retrieved November 11, 2006
  5. ↑ Шаблон:Citation
  6. ↑ Шаблон:Книга
  7. ↑ Шаблон:Книга
  8. ↑ Ошибка цитирования Неверный тег <ref>; для сносок AND16 не указан текст
  9. ↑ 9,0 9,1 Шаблон:Cite web
  10. ↑ Шаблон:Citation Шаблон:Wayback
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Принцип_Дирихле_(комбинаторика)&oldid=10647101