Войти
Голуби в норах. Здесь n = 10 голубей в m = 9 лунках. Поскольку 10 больше 9, принцип «голубятни» гласит, что по крайней мере в одной дыре может быть более одного голубя. (В верхнем левом отверстии находятся 2 голубя.) В математике принцип голубятни гласит, что if 
Хотя принцип ящика для ящиков появился еще в 1624 году в книге, приписываемой Жану Лерешону, его обычно называют принципом ящика Дирихле или принципом ящика Дирихле после трактовки этого принципа в 1834 году Петером Густавом Леженом Дирихле под названием Schubfachprinzip («принцип выдвижного ящика» или «принцип полки»).
Принцип имеет несколько обобщений и может быть заявлено по-разному. В более количественной версии: для натуральных чисел 
Хотя наиболее простым приложением является конечные наборы (например, голуби и коробки), он также используется с бесконечными наборами, которые нельзя поместить в взаимно-однозначная переписка. Для этого требуется формальная формулировка принципа "голубятни", который гласит: «Не существует инъективной функции, кодомен которого меньше, чем его домен ». Расширенные математические доказательства, такие как лемма Зигеля, основываются на этой более общей концепции.
Ящики для сообщений «голубятня» в Стэнфордском университете Дирихле публиковал свои работы на французском и немецком языках, используя немецкий Schubfach или французское tiroir. Строгое первоначальное значение этих терминов соответствует английскому ящику, то есть ящику с открытым верхом, который можно задвигать и извлекать из шкафа, в котором он находится. (Дирихле писал о распределении жемчуга по ящикам.) Эти термины были преобразованы в слово pigeonhole в смысле небольшого открытого пространства в письменном столе, шкафу или стене для хранения писем или бумаг, образно укорененных в структурах. это домашние голуби.
Поскольку мебель с ящиками для ящиков обычно используется для хранения или сортировки вещей по разным категориям (например, письма в почтовом отделении или ключи от номера в отеле), ячейка для перевода может быть более точной интерпретацией исходной метафоры ящика Дирихле.. Это понимание термина «голубятня», относящегося к некоторым деталям мебели, постепенно исчезает - особенно среди тех, кто не говорит по-английски, но является lingua franca в научном мире - в пользу более наглядной интерпретации, буквально с участием голубей и нор. Наводящее на размышления (хотя и не вводящее в заблуждение) толкование «голубятни» как «голубятни» недавно нашло свое отражение в немецком обратном переводе «принципа голубятни» как «Taubenschlagprinzip».
Помимо исходных терминов «Schubfachprinzip» на немецком языке и «Principe des tiroirs» на французском, другие буквальные переводы все еще используются в болгарском («принцип на чекмеджетата»), китайском («抽屉 原理»), датский ("Skuffeprincippet"), голландский ("ladenprincipe"), венгерский ("skatulyaelv"), итальянский ("Principio dei cassetti "), японский (" 引 き 出 し 論 法 "), персидский (" اصل لانه کبوتری "), польский (" zasada szufladkowa "), Шведский («Lådprincipen») и турецкий («çekmece ilkesi»).
Предположим, что в ящике есть смесь черных и синих носков, каждый из которых можно носить на любой ноге, и которые вы тянете. ряд носков из ящика, не глядя. Какое минимальное количество натянутых носков необходимо, чтобы пара была одного цвета? Используя принцип ячеек, чтобы иметь хотя бы одну пару одного цвета (m = 2 отверстия, по одному на цвет), используя по одному ящику для каждого цвета, вам нужно вытащить из ящика только три носка (n = 3 предмета). Либо у вас есть три предмета одного цвета, либо у вас есть два предмета одного цвета и один другого цвета.
Если есть n человек, которые могут пожать друг другу руки (где n>1), принцип ячейки показывает, что всегда есть пара людей, которые пожмут друг другу руки с таким же количеством людей. В этом применении принципа «дыра», к которой приписывается человек, - это количество рук, которые он пожимает. Поскольку каждый человек пожимает руку некоторому количеству людей от 0 до n - 1, существует n возможных отверстий. С другой стороны, либо отверстие «0», либо отверстие «n - 1» либо оба должны быть пустыми, поскольку невозможно (если n>1) кому-то пожать руку всем остальным, в то время как кто-то пожимает руку никто. Это оставляет n человек, которые должны быть помещены в самое большее n - 1 непустое отверстие, так что принцип применим.
Можно продемонстрировать, что в Лондоне должно быть как минимум два человека с одинаковым количеством волос на голове, следующим образом. Поскольку типичная человеческая голова имеет в среднем около 150 000 волос, разумно предположить (в качестве верхней границы), что ни у кого на голове не более 1 000 000 волос (m = 1 миллион дырок). В Лондоне более 1 000 000 человек (n больше 1 миллиона пунктов). Назначив ячейку для каждого количества волос на голове человека и распределив людей по ячейкам в соответствии с количеством волосков на голове, должно быть как минимум два человека, назначенных на одну ячейку в соответствии с 1 000 001-м заданием (поскольку у них есть одинаковое количество волосков на голове) (или, n>m). Для среднего случая (m = 150 000) с ограничением: наименьшее количество перекрытий, будет не более одного человека, назначенного на каждую ячейку, и 150 001 человек, назначенный на ту же ячейку, что и кто-то еще. При отсутствии этого ограничения могут быть пустые ячейки, потому что «столкновение» происходит перед 150 001-м человеком. Принцип просто доказывает существование перекрытия; в нем ничего не говорится о количестве перекрытий (которое подпадает под действие распределения вероятностей ).
В «Истории афинского общества» есть мимолетный сатирический намек на эту версию принципа с префиксом «Приложение к афинскому оракулу: сборник оставшихся вопросов и ответов в Старые Афинские Меркурии »(Отпечатано для Эндрю Белла, Лондон, 1710 г.). Кажется, вопрос в том, были ли в Мире какие-то два человека с одинаковым количеством волос на голове? был поднят в «Афинском Меркурии» до 1704 года.
Возможно, первое письменное упоминание о принципе «голубятни» появляется в 1622 году в коротком предложении латинского произведения «Selectposition Propositiones» французского иезуита Жана Лерешона, где он написал: «Необходимо, чтобы у двух мужчин было одинаковое количество волос, écus или других вещей друг у друга». Полный принцип был изложен двумя годами позже с дополнительными примерами в другой книге, которую часто приписывают Лерешону, но, возможно, она была написана одним из его учеников.
Задача дня рождения спрашивает для набора из n случайно выбранных людей, какова вероятность того, что у какой-то пары из них будет один и тот же день рождения? По принципу «ящика», если в комнате 367 человек, есть по крайней мере одна пара, у которой один день рождения, так как есть только 366 возможных дней рождения на выбор (включая 29 февраля, если он есть). «Парадокс» дня рождения относится к тому результату, что даже если группа состоит всего из 23 человек, вероятность того, что есть пара людей с одним днем рождения, все равно превышает 50%. Хотя на первый взгляд это может показаться удивительным, это интуитивно имеет смысл, если учесть, что на самом деле сравнение будет проводиться между всеми возможными парами людей, а не фиксировать одного человека и сравнивать его исключительно с остальной группой.
Представьте себе семь человек, которые хотят сыграть в командном турнире (n = 7 предметов), с ограничением выбора только четырьмя командами (m = 4 лунки). Принцип «ящика» говорит нам, что все они не могут играть за разные команды; должна быть как минимум одна команда, в которую входят как минимум двое из семи игроков:
Любое подмножество размера шесть из множества S = {1,2, 3,..., 9} должны содержать два элемента, сумма которых равна 10. Ячейки будут помечены двумя подмножествами элементов {1,9}, {2,8}, {3,7}, {4,6 } и синглтон {5}, всего пять ячеек. Когда шесть «голубей» (элементы подмножества шестого размера) помещаются в эти ячейки, и каждый голубь входит в ячейку, на этикетке которой он содержится, по крайней мере, одна из ячеек, помеченных двухэлементной подгруппой, будет иметь две ячейки. голубей в нем.
Этот принцип можно использовать для доказательства того, что любой алгоритм сжатия без потерь, при условии, что он уменьшает некоторые входные данные (как следует из названия сжатия), также сделает некоторые другие входы больше. В противном случае набор всех входных последовательностей до заданной длины L можно было бы сопоставить (намного) меньшему набору всех последовательностей длиной меньше L без коллизий (поскольку сжатие без потерь), возможность, которую исключает принцип ящика.
Важной проблемой в математическом анализе является для фиксированного иррационального числа a показать, что набор {[na]: n является целым числом} из дробные части - это плотная в [0, 1]. Оказывается, нелегко явно найти целые числа n, m такие, что | na - m | < e, where e>0 - небольшое положительное число, а - произвольное иррациональное число. Но если взять M такое, что 1 / M < e, by the pigeonhole principle there must be n1, n 2 ∈ {1, 2,..., M + 1} такое, что n 1 a и n 2 a находятся в одном и том же целочисленном подразделении размера 1 / M (между последовательными целыми числами есть только M таких подразделений). В частности, можно найти n 1, n 2 такие, что n 1 a находится в (p + k / M, p + (k + 1) / M), и n 2 a находится в (q + k / M, q + (k + 1) / M), для некоторых p, q целых чисел и k в {0, 1,..., М - 1}. Затем легко проверить, что (n 2 - n 1) a находится в (q - p - 1 / M, q - p + 1 / M). Это означает, что [na] < 1/M < e, where n = n2- n 1 или n = n 1 - n 2. Это показывает, что 0 является предельной точкой {[na]}. Затем можно использовать этот факт, чтобы доказать случай для p в (0, 1]: найти n такое, что [na] < 1/M < e; then if p ∈ (0, 1/M], the proof is complete. Otherwise p ∈ (j/M, (j + 1)/M], and by setting k = sup{r ∈ N : r[na] < j/M}, one obtains |[(k + 1)na] − p| < 1/M < e.
Варианты встречаются в ряде доказательств. В доказательстве леммы о накачке для регулярных языков, используется версия, в которой смешиваются конечные и бесконечные множества: если бесконечно много объектов помещается в конечное число ящиков, тогда существуют два объекта, которые разделяют ящик. В решении Фиском проблемы Художественная галерея используется своего рода обратное: если n объектов помещаются в k ящиков, то есть ящик, содержащий не более n / k объектов.
Ниже приведены альтернативные формулировки принцип «голубятни».
Пусть q 1, q 2,..., q n - натуральные числа. Если
объекты распределяются по n боксов, то либо первый блок содержит не менее q 1 объектов, либо второй блок содержит не менее q 2 объектов,..., либо n-й блок содержит не менее q n объектов.
Простая форма получается из этого, если q 1 = q 2 =... = q n = 2, что дает n + 1 объект. Принятие q 1 = q 2 =... = q n = r дает более количественную версию принципа, а именно:
Пусть n и r - натуральные числа. Если n (r - 1) + 1 объектов распределены в n блоков, то по крайней мере один из блоков содержит r или более объектов.
Это также может быть указано как, если k дискретных объектов должны быть быть распределенным по n контейнерам, то хотя бы один контейнер должен содержать не менее 
Вероятностное обобщение принципа голубятни гласит, что если n голубей случайным образом помещены в m почтовых ящиков с равномерной вероятностью 1 / m, то по крайней мере в одном голубятне будет больше чем один голубь с вероятностью
где (m) n - факториал падения m (m - 1) (m - 2)... (m - n + 1). Для n = 0 и для n = 1 (и m>0) эта вероятность равна нулю; Другими словами, если голубь один, конфликта быть не может. Для n>m (больше голубей, чем ячеек) он равен единице, и в этом случае он совпадает с обычным принципом ячейки. Но даже если количество голубей не превышает количества ячеек (n ≤ m), из-за случайного характера распределения голубей по ячейкам часто существует значительная вероятность столкновения. Например, если 2 голубя случайным образом распределяются по 4 ячейкам, существует 25% -ная вероятность, что хотя бы одна ячейка будет содержать более одного голубя; для 5 голубей и 10 лунок эта вероятность составляет 69,76%; а для 10 голубей и 20 лунок - около 93,45%. Если количество отверстий остается фиксированным, всегда больше вероятность пары, когда вы добавляете больше голубей. Эта проблема гораздо более подробно рассматривается в парадоксе дня рождения.
. Дальнейшее вероятностное обобщение состоит в том, что, когда действительная случайная величина X имеет конечное среднее E ( X), то ненулевая вероятность того, что X больше или равно E (X), и аналогично ненулевая вероятность того, что X меньше или равно E (X). Чтобы увидеть, что это подразумевает стандартный принцип ячеек, возьмите любое фиксированное расположение n голубей в m отверстий и пусть X будет числом голубей в ямке, выбранным равномерно и случайным образом. Среднее значение X равно n / m, поэтому, если голубей больше, чем нор, среднее значение больше единицы. Следовательно, X иногда не меньше 2.
Принцип «голубятни» можно расширить до бесконечных множеств, сформулировав его в терминах количественных чисел : если мощность множества 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 пиков на детекторе; эти пики являются результатом четырех возможных взаимодействий, которые может испытать каждый электрон (отдельно, только вместе с первой другой частицей, только вместе со второй другой частицей, или все три вместе). Если бы сила взаимодействия была довольно низкой, как это было бы во многих реальных экспериментах, отклонение от картины нулевого взаимодействия было бы почти незаметным, намного меньше, чем период решетки атомов в твердых телах, таких как детекторы, используемые для наблюдения этих закономерностей. Это сделало бы очень трудным или даже невозможным отличить слабую, но ненулевую силу взаимодействия от вообще отсутствующего взаимодействия и, таким образом, создавало бы иллюзию трех электронов, которые не взаимодействовали, несмотря на то, что все три проходили по двум путям.
