Принцип Дирихле

Принцип Дирихле — это фундаментальное утверждение комбинаторики, которое в простейшей формулировке гласит: если в n ящиков разложить n+1 предметов, то хотя бы в одном ящике окажется не менее двух предметов. Более общая формулировка: если n предметов распределить по m ящикам, причём n > m, то хотя бы один ящик будет содержать не менее ⌈n/m⌉ предметов. Принцип назван в честь немецкого математика Петера Густава Лежёна Дирихле, который впервые применил его в 1834 году при доказательстве теоремы о приближении иррациональных чисел рациональными.

История

Идея, лежащая в основе принципа, была известна ещё в древности. Например, в «Книге о числах» (XIII век) итальянского математика Леонардо Фибоначчи встречается задача, решаемая с помощью этого рассуждения. Однако в явном виде принцип был сформулирован и систематически использован Петером Густавом Лежёном Дирихле в работе «О существовании обратных функций в теории чисел» (1834). Дирихле применил его для доказательства того, что для любого иррационального числа α существует бесконечно много рациональных приближений p/q, таких что |α — p/q| < 1/q². Впоследствии принцип стал важным инструментом в комбинаторике, теории чисел, теории графов и других разделах математики.

В русскоязычной литературе принцип часто называют «принципом ящиков Дирихле» или «принципом голубей и ячеек» (pigeonhole principle). В англоязычной традиции распространены названия «pigeonhole principle» и «Dirichlet’s box principle».

Формулировки

Простейшая формулировка

Если n+1 предметов разложить в n ящиков, то хотя бы один ящик содержит не менее двух предметов.

Обобщённая формулировка

Если n предметов распределить по m ящикам, причём n > m, то хотя бы один ящик содержит не менее ⌈n/m⌉ предметов. Здесь ⌈x⌉ — округление вверх до ближайшего целого.

Комбинаторная формулировка

Если функция f отображает множество A мощности |A| = n в множество B мощности |B| = m, и n > m, то f не является инъективной — существуют два различных элемента a₁, a₂ ∈ A, такие что f(a₁) = f(a₂).

Строгая формулировка

Для любых натуральных чисел n и m, если n > m, то любое отображение n-элементного множества в m-элементное множество не является инъективным.

Доказательство

Принцип Дирихле является тривиальным следствием определения мощности множества и не требует сложного доказательства. Допустим противное: пусть n предметов разложены по m ящикам, и в каждом ящике не более одного предмета. Тогда общее количество предметов не превышает m. Но по условию n > m, что противоречит предположению. Следовательно, хотя бы один ящик содержит не менее двух предметов.

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

В комбинаторике

Задача о рукопожатиях. В группе из 6 человек каждый пожал руку некоторому числу других (от 0 до 5). Докажите, что найдутся два человека, пожарших рук одинаковое количество раз. Решение: возможные числа рукопожатий — 0, 1, 2, 3, 4, 5 (всего 6 вариантов). Но если кто-то пожал руку 5 раз, то никто не мог пожать руку 0 раз (так как все, кроме него, пожали руку хотя бы ему). Таким образом, реально возможных вариантов не более 5, а людей 6 — по принципу Дирихле, два человека имеют одинаковое число рукопожатий.

Задача о носках. В ящике лежат 10 красных и 10 синих носков. Сколько носков нужно вытащить наугад, чтобы гарантированно получить пару одного цвета? Решение: цвета два (красный и синий). Если вытащить 3 носка, то по принципу Дирихле хотя бы два из них будут одного цвета.

В теории чисел

Теорема Дирихле о приближении. Для любого иррационального числа α существует бесконечно много рациональных чисел p/q, таких что |α — p/q| < 1/q². Доказательство: рассмотрим числа {kα} (дробные части) для k = 0, 1, …, N. Разобьём отрезок [0, 1] на N равных частей. По принципу Дирихле, среди N+1 чисел две дробные части попадут в один отрезок, откуда следует существование нужного приближения.

Доказательство бесконечности простых чисел (альтернативное). Предположим, что простых чисел конечное множество: p₁, p₂, …, pₖ. Рассмотрим число N = p₁·p₂·…·pₖ + 1. Оно не делится ни на одно из простых pᵢ, но должно иметь простой делитель, который не входит в исходный список — противоречие. Хотя это доказательство не использует принцип Дирихле напрямую, оно иллюстрирует похожий логический приём.

В теории графов

Лемма о рукопожатиях. В любом графе сумма степеней всех вершин чётна и равна удвоенному числу рёбер. Следствие: в любом графе количество вершин нечётной степени чётно. Доказательство этого следствия можно провести с использованием принципа Дирихле: если бы вершин нечётной степени было нечётное количество, то сумма степеней была бы нечётной, что невозможно.

Задача о компании. В компании из 6 человек либо найдутся трое попарно знакомых, либо трое попарно незнакомых. Доказательство: выберем одного человека. Среди остальных 5 он либо знаком с тремя, либо не знаком с тремя. В первом случае среди этих трёх либо есть пара знакомых (тогда вместе с выбранным образуется тройка знакомых), либо все трое попарно незнакомы. Во втором случае аналогично. Это частный случай теоремы Рамсея, и принцип Дирихле используется на первом шаге.

В информатике

Хеш-функции. Принцип Дирихле лежит в основе неизбежности коллизий в хеш-таблицах: если количество возможных ключей превышает количество ячеек таблицы, то коллизия гарантирована.

Сжатие данных. Невозможность сжатия всех данных без потерь: если количество возможных сообщений длины n больше количества возможных сжатых сообщений длины m < n, то по принципу Дирихле два разных сообщения будут сжаты в один и тот же код, что приведёт к потере информации.

Обобщения и вариации

Принцип Дирихле для бесконечных множеств

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

Принцип Дирихле для меры

Если отрезок длины L разбит на n отрезков, то хотя бы один из них имеет длину не менее L/n. Аналогично для площади, объёма и других мер.

Комбинаторный принцип Дирихле в усиленной форме

Если n предметов разложить по m ящикам, то найдётся ящик, содержащий не менее ⌈n/m⌉ предметов, и ящик, содержащий не более ⌊n/m⌋ предметов. Здесь ⌊x⌋ — округление вниз.

Принцип Дирихле в теории вероятностей

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

Критика и ограничения

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

Интересные факты

• В англоязычной литературе принцип часто иллюстрируют примером с голубями и ячейками: если 10 голубей сидят в 9 ячейках, то в одной ячейке сидит не менее двух голубей.
• Принцип Дирихле является частным случаем более общего принципа — «принципа крайнего», который утверждает, что в любой конечной системе существует элемент с экстремальным свойством.
• В 1995 году принцип Дирихле был использован для доказательства того, что в любом множестве из 5 точек на плоскости, никакие три из которых не лежат на одной прямой, найдётся выпуклый четырёхугольник (теорема Эрдёша — Секереша для n=5).
• Принцип Дирихле лежит в основе «парадокса дней рождения»: в группе из 23 человек вероятность того, что у двух человек совпадает день рождения, превышает 50%. Это не прямое применение принципа, а его вероятностный аналог.

Источники

1. Дирихле П. Г. Л. «О существовании обратных функций в теории чисел» (1834).
2. Холл М. «Комбинаторика». — М.: Мир, 1970.
3. Рыбников К. А. «Введение в комбинаторный анализ». — М.: Изд-во МГУ, 1985.
4. Грэхем Р., Кнут Д., Паташник О. «Конкретная математика». — М.: Мир, 1998.
5. Эрдёш П., Секереш Д. «О выпуклых многоугольниках» (1935).