Суть правила на простых числах
Представь четыре яблока и три кармана. Даже если ты аккуратно разложишь по одному яблоку в каждый карман, у тебя останется ещё одно лишнее яблоко. Куда бы ты его ни положил, в каком-то кармане неизбежно окажется пара. В математике это правило формулируют строго, но его фундамент доступен даже первокласснику.
Впервые это очевидное наблюдение как строгий научный инструмент применил немецкий математик Петер Густав Лежён Дирихле в 1834 году. Он использовал его в теории чисел, назвав метод принципом ящиков. Во многих странах, включая Англию и США, это утверждение называют принципом голубей и ящиков (pigeonhole principle). В русскоязычной традиции закрепился образ кроликов и клеток, который придумали популяризаторы науки для школьных кружков.
Математическое доказательство от противного
Хотя вывод кажется очевидным, в геометрии и комбинаторике его требуется строго обосновывать. Доказывается принцип Дирихле методом от противного. Это один из базовых приёмов математической логики.
Допустим, у нас есть N клеток и N плюс один кролик. Предположим обратное, будто ни в одной клетке нет двух или больше кроликов. Это означает, что в каждой клетке сидит максимум один кролик или клетка вообще пустует. Посчитаем общее количество животных при таком раскладе. В N клетках может поместиться максимум N кроликов. Но у нас на руках изначально было N плюс один кролик. Получилось противоречие с исходным условием задачи. Следовательно, наше предположение неверно, и хотя бы в одной клетке действительно сидят два или более кролика.
Обобщенный принцип Дирихле
Классическое правило говорит о перевесе всего на один предмет, но в реальных задачах кроликов бывает значительно больше. В таких ситуациях работает обобщенная форма закона.
Пусть у нас есть k клеток и n кроликов. Если мы разделим n на k, то найдем среднее число животных на одно место. Принцип гласит, что найдется хотя бы одна клетка, где сидит не меньше, чем результат деления n на k, округленный вверх до целого числа.
Разберем эту формулу на конкретной школьной ситуации. В классе учится 25 человек. Месяцев в году всего 12. Делим 25 учеников на 12 месяцев. Получаем 2 целых и одну двенадцатую. Округляем в большую сторону и получаем число 3. Значит, в этом классе обязательно найдутся минимум трое ребят, которые празднуют день рождения в один и тот же месяц.
Как находить кроликов и клетки в сложных задачах
Главная сложность олимпиадных заданий заключается в том, что в тексте нет ни слова про ящики или животных. Математик должен сам догадаться, какие объекты выступают кроликами, а какие свойства служат клетками.
Задачи на делимость чисел
Возьмем любые три целых числа. Можно утверждать, что сумма каких-то двух из них обязательно окажется четной. Роль клеток здесь играют остатки от деления на 2. При делении любого числа на 2 получается либо остаток 0 для четных чисел, либо остаток 1 для нечетных чисел. Всего существует 2 варианта остатка.
У нас есть три выбранных числа. Чисел три, а возможных остатков всего два. По принципу Дирихле среди трех чисел найдутся минимум два числа с одинаковым остатком. Сумма двух четных чисел всегда дает четное число. Сумма двух нечетных чисел тоже всегда дает четное число. Утверждение полностью доказано.
Геометрические задачи
Представь равносторонний треугольник со стороной 1 метр. Внутри него случайным образом бросили 5 точек. Можно гарантировать, что расстояние между какими-то двумя точками будет строго меньше 0,5 метра.
Чтобы это доказать, разделим исходный треугольник средними линиями на 4 одинаковых маленьких равносторонних треугольника. Длина стороны каждого такого треугольника составляет ровно 0,5 метра. Эти 4 треугольника становятся нашими клетками, а 5 брошенных точек становятся кроликами.
Пять точек распределяются по четырем фигурам. По принципу Дирихле хотя бы в один маленький треугольник попадут минимум две точки. Максимальное расстояние между любыми точками внутри треугольника со стороной 0,5 метра не превышает длины его стороны. Значит, расстояние между этими двумя точками не может быть больше половины метра.
Применение правила в информатике и криптографии
Принцип Дирихле лежит в основе работы компьютерных алгоритмов сжатия данных и алгоритмов хеширования. Любая программа для сжатия файлов берет длинную цепочку битов и пытается упаковать ее в более короткую. Число коротких файлов строго ограничено объемом доступных комбинаций байтов.
Поскольку вариантов исходных файлов бесконечно много, а вариантов сжатых файлов заданного размера конечное число, невозможно создать архиватор, способный сжать абсолютно любой файл. Если бы такой архиватор существовал, по принципу Дирихле двум совершенно разным файлам присвоился бы один и тот же сжатый архив, и восстановить исходные данные без ошибок стало бы невозможно. Это математическое ограничение называют коллизией.
Частые вопросы
Можно ли применять принцип Дирихле для бесконечного числа предметов?
Да, существует версия принципа для бесконечных множеств. Если бесконечное множество элементов разбить на конечное число групп, то как минимум в одной группе обязательно окажется бесконечно много элементов.
Сколько человек нужно собрать в комнате, чтобы у двоих совпал день рождения?
Для стопроцентной математической гарантии по принципу Дирихле нужно 367 человек, с учетом високосного года из 366 дней. В теории вероятностей есть похожий парадокс дней рождения, где 50 процентов вероятности совпадения достигается уже при 23 людях, но жесткую гарантию дает именно число 367.
Как понять, что в задаче нужно использовать именно этот метод?
Ищи в вопросе задачи характерные фразы: «докажите, что найдутся хотя бы двое», «существуют ли одинаковые», «всегда ли верно, что среди выбранных есть пара». Такие формулировки прямо указывают на перебор конечных состояний через ящики и предметы.