Введение

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

В математике принцип Дирихле (также известный как принцип голубиных ящиков) гласит, что если n предметов поместить в m контейнеров, где n > m, то по крайней мере в одном контейнере окажется больше одного предмета. Например, из трех перчаток (ни одна из которых не является универсальной), по крайней мере две должны быть правыми или по крайней мере две – левыми, поскольку есть три объекта, но только две категории – правосторонняя и левосторонная. Это, на первый взгляд, очевидное утверждение, являющееся разновидностью комбинаторного аргумента, может использоваться для доказательства неожиданных результатов. Например, если население Лондона превышает максимальное количество волос, которое может быть у человека, на единицу, то принцип Дирихле утверждает, что в Лондоне найдется как минимум два человека с одинаковым количеством волос на голове. Хотя принцип Дирихле впервые был сформулирован в 1624 году Жаном Леурэшоном, он чаще всего называется принципом ящика Дирихле или принципом полки Дирихле, по названию работы Питера Густава Лежена Дирихле 1834 года под названием Schubfachprinzip («принцип ящика» или «принцип полки»). Принцип имеет множество обобщений и может быть сформулирован различными способами. В более строгой форме: для натуральных чисел k и m, если n = km + 1 объектов распределены по m множествам, то принцип Дирихле утверждает, что по крайней мере в одном из множеств будет содержаться не менее k + 1 объекта. Для произвольных n и m это обобщается до , где и обозначают функции взятия целой части и округления вверх соответственно. Хотя наиболее прямое применение принципа связано с конечными множествами (например, голубями и ящиками), он также используется для бесконечных множеств, которые нельзя привести к взаимно однозначному соответствию. Для этого требуется формальная формулировка принципа Дирихле: «не существует инъективной функции, кообласть которой меньше области определения». Продвинутые математические доказательства, такие как лемма Зигеля, основаны на этой более общей концепции.

Этимология

Дирихле опубликовал свои работы как на французском, так и на немецком языках, используя немецкий Schubfach или французский [[wikt:tiroir. Изначальное значение этих терминов соответствует английскому слову drawer, то есть открытому ящику, который можно выдвигать и задвигать в шкаф, в котором он находится. (Дирихле писал о распределении жемчужин по ящикам.) Эти термины трансформировались в «голубиную ячейку» в значении небольшого открытого пространства в столе, шкафу или стене для хранения писем или бумаг, метафорически связанного с конструкциями для содержания голубей. Поскольку мебель с голубиными ячейками обычно используется для хранения или сортировки вещей по множеству категорий (например, писем на почте или ключей от номеров в отеле), перевод «голубиная ячейка» может быть более точным отражением оригинального «ящика» Дирихле. Понимание этого термина как относящегося к элементам мебели постепенно уходит в прошлое – особенно среди тех, кто не владеет английским языком как родным, но использует его в качестве лингва франка в научном мире – уступая место более образной интерпретации, буквально включающей голубей и отверстия. Недавно появившаяся, хотя и не вводящая в заблуждение, интерпретация «pigeonhole» как «dovecote» (голубятни) привела к обратному переводу «принципа голубя» на немецкий язык как «Taubenschlagprinzip». Помимо оригинальных терминов «Schubfachprinzip» на немецком и «Principe des tiroirs» на французском, другие буквальные переводы до сих пор используются на арабском («مبدأ برج الحمام»), болгарском («принцип на чекмеджетата»), китайском («抽屉原理»), датском («Skuffeprincippet»), голландском («ladenprincipe»), венгерском («skatulyaelv»), итальянском («principio dei cassetti»), японском («引き出し論法»), персидском («اصل لانه کبوتری»), польском («zasada szufladkowa»), португальском («Princípio das Gavetas»), шведском («Lådprincipen»), турецком («çekmece ilkesi») и вьетнамском («nguyên lý hộp»).

Выбираю носки

Предположим, в ящике находится смесь черных и синих носков, каждый из которых можно надеть на любую ногу. Вы вытаскиваете несколько носков из ящика, не глядя. Какое минимальное количество вытащенных носков необходимо, чтобы гарантированно получить пару одного цвета? По принципу Дирихле (используя одну «голубиную ячейку» для каждого цвета), ответ – три носка. Либо у вас будет три носка одного цвета, либо два носка одного цвета и один носка другого цвета.

Пожимание рук

Если n человек могут пожать друг другу руки (где n > 1), принцип Дирихле показывает, что всегда найдется пара людей, которые пожмут руки с одинаковым количеством людей. В данном применении принципа "ячейкой", в которую помещают человека, является число рукопожатий этого человека. Поскольку каждый человек может пожать руку от 0 до n − 1 людям, существует n возможных ячеек. С другой стороны, либо ячейка "0", либо ячейка "n − 1", либо обе должны быть пустыми, так как невозможно (при n > 1), чтобы кто-то пожал руки всем остальным, а кто-то при этом не пожал ни одной руки. Таким образом, n человек нужно распределить по максимум n − 1 незаполненным ячейкам, что и позволяет применить принцип Дирихле. Этот пример с рукопожатиями эквивалентен утверждению, что в любом графе с более чем одной вершиной найдется хотя бы одна пара вершин с одинаковой степенью. Это можно увидеть, сопоставив каждого человека с вершиной, а каждое рукопожатие – с ребром.

Подсчет волос

Можно продемонстрировать, что в Лондоне должно быть по крайней мере два человека с одинаковым количеством волос на голове. Поскольку типичная человеческая голова содержит в среднем около 150 000 волос, разумно предположить (в качестве верхней границы), что у кого-либо не может быть более 1 000 000 волос на голове. В Лондоне проживает более 1 000 000 человек (n больше 1 миллиона). Если каждому возможному количеству волос на голове сопоставить «ячейку», а затем распределить людей по этим ячейкам в зависимости от количества волос на их голове, то, начиная с 1 000 001-го человека, как минимум два человека окажутся в одной и той же ячейке (потому что у них одинаковое количество волос; или, n > m). Если предположить, что в Лондоне проживает 9,002 миллиона человек, то следует, что по крайней мере у десяти лондонцев одинаковое количество волос, так как размещение девяти лондонцев в каждой из миллиона ячеек охватывает только 9 миллионов человек. В среднем случае (при m = 150 000) и при условии минимизации совпадений, в каждой ячейке будет находиться не более одного человека, а 150 001-й человек попадет в ячейку, уже занятую другим. Без этого ограничения некоторые ячейки могут остаться пустыми, поскольку «столкновение» может произойти раньше, чем будет распределен 150 001-й человек. Принцип лишь доказывает существование совпадения; он ничего не говорит о количестве совпадений (что относится к области теории вероятностей). В английской литературе есть мимолетная сатирическая отсылка к этой версии принципа в «Истории афинского общества», которая предшествует «Дополнению к афинскому оракулу: Сборнику оставшихся вопросов и ответов из старых афинских «Меркуриев»» (изданному для Эндрю Белла, Лондон, 1710). Похоже, что вопрос о том, существуют ли в мире два человека с одинаковым количеством волос на голове, был поднят в «Афинских Меркуриях» до 1704 года. Возможно, первое письменное упоминание принципа ящиков встречается в коротком предложении из работы французского иезуита Жана Леурхона «Selectæ Propositiones» 1622 года. Полная формулировка принципа была представлена два года спустя, с дополнительными примерами, в другой книге, которую часто приписывают Леурхону, но автором которой мог быть один из его учеников.

Альтернативные формулировки

Ниже приведены альтернативные формулировки принципа Дирихле. Если n объектов распределены по m ячейкам, и если n > m, то хотя бы в одной ячейке окажется не менее двух объектов. (обобщение 4) Если S и T – множества, и мощность S меньше мощности T, то не существует сюръективного отображения из S в T.

Сильная форма

Пусть q1, q2, ..., qn – положительные целые числа. Если объекты распределены по n ящикам, то либо первый ящик содержит по крайней мере q1 объектов, либо второй ящик содержит по крайней мере q2 объектов, ..., либо n-й ящик содержит по крайней мере qn объектов. Простая форма получается, если принять q1 = q2 = ... = qn = 2, что дает n + 1 объект. Если принять q1 = q2 = ... = qn = r, то получается более количественная версия принципа, а именно:

Пусть n и r – положительные целые числа. Если n(r – 1) + 1 объектов распределены по n ящикам, то по крайней мере один из ящиков содержит r или более объектов. Это также можно сформулировать так: если k дискретных объектов нужно распределить по n контейнерам, то по крайней мере один контейнер должен содержать не менее ⌈k/n⌉ объектов, где ⌈x⌉ – функция потолка, обозначающая наименьшее целое число, большее или равное x. Аналогично, по крайней мере один контейнер должен содержать не более чем ⌊k/n⌋ объектов, где ⌊x⌋ – функция пола, обозначающая наибольшее целое число, меньшее или равное x.

Бесконечные множества

Принцип Дирихле может быть расширен на бесконечные множества, формулируя его в терминах кардинальных чисел: если кардинальность множества A больше кардинальности множества B, то не существует инъекции из A в B. Однако в такой формулировке принцип является тавтологическим, поскольку само определение того, что кардинальность множества A больше кардинальности множества B, означает отсутствие инъективного отображения из A в B. При этом добавления хотя бы одного элемента к конечному множеству достаточно для увеличения его кардинальности. Другая формулировка принципа Дирихле для конечных множеств аналогична принципу, согласно которому конечные множества являются дедекиндовски конечными: пусть A и B – конечные множества. Если существует сюръекция из A в B, которая не является инъективной, то никакая сюръекция из A в B не будет инъективной. Более того, никакая функция из A в B не будет инъективной. Это неверно для бесконечных множеств: рассмотрим функцию на натуральных числах, которая отображает 1 и 2 в 1, 3 и 4 в 2, 5 и 6 в 3 и так далее. Существует аналогичный принцип для бесконечных множеств: если несчетное количество голубей поместить в счетное количество голубятен, то найдется хотя бы одна голубятня, в которой окажется несчетное количество голубей. Однако этот принцип не является обобщением принципа Дирихле для конечных множеств: он, как правило, неверен для конечных множеств. В техническом плане это означает, что если A и B – конечные множества, такие, что любая сюръективная функция из A в B не является инъективной, то существует элемент b из B, для которого существует биекция между прообразом b и A. Это существенно другое утверждение, которое становится абсурдным при больших конечных кардинальностях.

Квантовая механика

Якир Ахаронов и др. представили аргументы о том, что квантовая механика может нарушать принцип Дирихле (принцип голубиной клетки), и предложили интерферометрические эксперименты для проверки этого принципа в квантовой механике. Последующие исследования поставили этот вывод под сомнение. В препринте на arXiv от января 2015 года исследователи Алястер Рэй и Тед Форган из Университета Бирмингема провели теоретический анализ волновой функции, используя стандартный принцип Дирихле, для описания траектории электронов с различными энергиями в интерферометре. Если бы электроны не взаимодействовали вовсе, каждый из них создал бы один идеально круглый пик. При высокой интенсивности взаимодействия каждый электрон формирует четыре различных пика, что в сумме дает 12 пиков на детекторе; эти пики являются результатом четырех возможных вариантов взаимодействия для каждого электрона (одиночно, только с первой другой частицей, только со второй другой частицей или со всеми тремя вместе). Если интенсивность взаимодействия была бы относительно низкой, как это обычно бывает в реальных экспериментах, отклонение от картины, соответствующей отсутствию взаимодействия, было бы практически незаметным, значительно меньше, чем межатомное расстояние в твердых телах, например, в детекторах, используемых для регистрации этих картин. Это затруднило бы или сделало бы невозможным различение слабой, но ненулевой интенсивности взаимодействия и полного отсутствия взаимодействия, создавая иллюзию того, что три электрона не взаимодействовали, несмотря на то, что все они прошли через два пути.