Принцип ящика

Голуби в норах. Здесь $n = 10$ голубей в $m = 9$ норах. Поскольку 10 больше 9, принцип нор гласит, что по крайней мере в одной норке находится больше одного голубя. (В верхней левой норке находится 2 голубя.)

В математике принцип ящика гласит, что если $n$ предметов помещаются в $m$ контейнеров, причем $n > m$ , то по крайней мере один контейнер должен содержать более одного предмета. ^[1] Например, из трех перчаток (ни одна из которых не является двусторонней/двухсторонней) по крайней мере две должны быть правыми или по крайней мере две должны быть левыми, потому что есть три предмета, но только две категории ручности, в которые их можно положить. Это, казалось бы, очевидное утверждение, тип аргумента подсчета , может быть использовано для демонстрации возможных неожиданных результатов. Например, учитывая, что население Лондона более чем на одну единицу превышает максимальное количество волос, которое может быть на голове человека, принцип требует, чтобы в Лондоне было по крайней мере два человека с одинаковым количеством волос на голове.

Хотя принцип ящика появился еще в 1624 году в книге, приписываемой Жану Лерешону , ^[2] его обычно называют принципом ящика Дирихле или принципом ящика Дирихле после трактовки принципа в 1834 году Петером Густавом Леженом Дирихле под названием Schubfachprinzip («принцип ящика» или «принцип полки»). ^[3]

Принцип имеет несколько обобщений и может быть сформулирован различными способами. В более количественной версии: для натуральных чисел $k$ и $m$ , если $n = km + 1$ объектов распределены по $m$ наборам, принцип ящика утверждает, что по крайней мере один из наборов будет содержать по крайней мере $k + 1$ объектов. ^[4] Для произвольных $n$ и $m$ это обобщается до , где и обозначают функции пола и потолка соответственно. $k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil$ $\lfloor \cdots \rfloor$ $\lceil \cdots \rceil$

Хотя наиболее простое применение принципа — к конечным множествам (таким как голуби и ящики), он также используется с бесконечными множествами , которые не могут быть приведены в соответствие один к одному . Для этого требуется формальное утверждение принципа ящика: «не существует инъективной функции , область определения которой меньше ее области определения ». Расширенные математические доказательства, такие как лемма Зигеля, строятся на этой более общей концепции.

Этимология

Дирихле публиковал свои работы на французском и немецком языках, используя либо немецкое Schubfach , либо французское tiroir . Строгое первоначальное значение этих терминов соответствует английскому drawer , то есть открытому ящику, который можно вставлять и выдвигать из шкафа, в котором он находится . (Дирихле писал о распределении жемчужин по ящикам.) Эти термины трансформировались в pigeonhole в значении небольшого открытого пространства в столе, шкафу или стене для хранения писем или бумаг , метафорически укорененного в сооружениях, в которых живут голуби.

Поскольку мебель с ячейками обычно используется для хранения или сортировки вещей по многим категориям (например, письма на почте или ключи от номера в отеле), перевод pigeonhole может быть лучшим представлением оригинального "drawer" Дирихле. Такое понимание термина pigeonhole , относящегося к некоторым особенностям мебели, исчезает — особенно среди тех, кто не говорит по-английски как по-родному, но как на lingua franca в научном мире — в пользу более образной интерпретации, буквально включающей голубей и ямы. Наводящая на размышления (хотя и не вводящая в заблуждение) интерпретация "pigeonhole" как " dovecote " в последнее время нашла свой путь обратно в немецкий обратный перевод "pigeonhole principle" как " Taubenschlagprinzip ". ^[5]

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

Примеры

Сбор носков

Предположим, что в ящике лежит смесь черных и синих носков, каждый из которых можно носить на любой ноге. Вы достаете несколько носков из ящика, не глядя. Какое минимальное количество вытащенных носков требуется, чтобы гарантированно получить пару одного цвета? По принципу ящика ( $m = 2$ , используя один ящик на цвет), ответ — три ( $n = 3$ предмета). Либо у вас три одного цвета, либо у вас есть два одного цвета и один другого.

Рукопожатие

Если $n$ человек могут пожать друг другу руки (где $n > 1$ ), принцип ящика показывает, что всегда найдется пара людей, которые пожмут руки одинаковому количеству людей. В этом применении принципа «ячейка», к которой приписан человек, — это количество рук, которые он пожимает. Поскольку каждый человек пожимает руки некоторому количеству людей от 0 до $n - 1$ , существует $n$ возможных ячеек. С другой стороны, либо ячейка «0», либо ячейка $« n - 1»$ , либо обе должны быть пустыми, поскольку невозможно (если $n > 1$ ) для какого-то человека пожать руки всем остальным, в то время как какой-то человек не пожимает руки никому. Это оставляет $n$ человек, которых можно поместить максимум в $n - 1$ непустых ячеек, поэтому принцип применяется.

Этот пример рукопожатия эквивалентен утверждению, что в любом графе с более чем одной вершиной существует по крайней мере одна пара вершин, которые имеют одинаковую степень . ^[8] Это можно увидеть, связав каждого человека с вершиной, а каждое ребро — с рукопожатием.

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

Можно продемонстрировать, что в Лондоне должно быть по крайней мере два человека с одинаковым количеством волос на голове следующим образом. ^[9]^[10] Поскольку на типичной человеческой голове в среднем около 150 000 волос, разумно предположить (в качестве верхней границы), что ни у кого нет более 1 000 000 волос на голове $(m = 1 миллион$ отверстий). В Лондоне проживает более 1 000 000 человек ( $n$ больше 1 миллиона элементов). Назначая ячейку каждому количеству волос на голове человека и распределяя людей по ячейкам в соответствии с количеством волос на их головах, должно быть по крайней мере два человека, назначенных на одну и ту же ячейку 1 000 001-м назначением (потому что у них одинаковое количество волос на голове; или $n > m$ ). Если предположить, что в Лондоне проживает 9,002 миллиона человек, ^[11] то из этого следует, что по крайней мере у десяти лондонцев одинаковое количество волос, поскольку девять лондонцев в каждой из 1 миллиона ячеек составляют всего 9 миллионов человек.

Для среднего случая ( $m = 150 000$ ) с ограничением: наименьшее количество совпадений, будет максимум один человек, назначенный в каждую ячейку, и 150 001-й человек, назначенный в ту же ячейку, что и кто-то еще. При отсутствии этого ограничения могут быть пустые ячейки, потому что «столкновение» происходит до 150 001-го человека. Принцип просто доказывает существование совпадения; он ничего не говорит о количестве совпадений (что относится к предмету распределения вероятностей ).

В английском языке есть мимолетный сатирический намек на эту версию принципа в «Истории афинского общества» , предваряющий «Дополнение к Афинскому оракулу: собрание оставшихся вопросов и ответов в старом Афинском Меркурии» (напечатано для Эндрю Белла, Лондон, 1710). ^[12] Кажется, вопрос о том, существуют ли в мире два человека с одинаковым числом волос на голове, был поднят в «Афинском Меркурии» до 1704 года. ^[13]^[14]

Возможно, первое письменное упоминание принципа «ящика» появляется в коротком предложении из работы французского иезуита Жана Лерешона 1622 года Selectæ Propositiones : ^[2] «Необходимо, чтобы у двух людей было одинаковое количество волос, écus или других вещей». ^[15] Полный принцип был изложен два года спустя, с дополнительными примерами, в другой книге, которую часто приписывают Лерешону, но, возможно, ее написал один из его учеников. ^[2]

Проблема дня рождения

Задача о днях рождения спрашивает, для набора из $n$ случайно выбранных людей, какова вероятность того, что у какой-то пары из них будет одинаковый день рождения? Сама задача в основном касается контринтуитивных вероятностей, но мы также можем сказать по принципу ящика, что среди 367 человек есть по крайней мере одна пара людей, которые разделяют один и тот же день рождения с вероятностью 100%, поскольку есть только 366 возможных дней рождения, из которых можно выбирать.

Командный турнир

Представьте себе семь человек, которые хотят играть в турнире команд $(n = 7$ предметов), с ограничением только на четыре команды $(m = 4$ лунки) на выбор. Принцип ящика говорит нам, что они не могут все играть за разные команды; должна быть по крайней мере одна команда, в которой есть по крайней мере два из семи игроков:

\left\lfloor {\frac {n-1}{m}}\right\rfloor +1=\left\lfloor {\frac {7-1}{4}}\right\rfloor +1=\left\lfloor {\frac {6}{4}}\right\rfloor +1=1+1=2

Сумма подмножества

Любое подмножество размера шесть из множества $S$ = {1,2,3,...,9} должно содержать два элемента, сумма которых равна 10. Ячейки будут помечены двумя подмножествами элементов {1,9}, {2,8}, {3,7}, {4,6} и синглтоном {5}, всего пять ячеек. Когда шесть «голубей» (элементы подмножества размера шесть) помещаются в эти ячейки, каждый голубь, попадающий в ячейку, в метке которой он содержится, по крайней мере одна из ячеек, помеченных подмножеством из двух элементов, будет иметь двух голубей. ^[16]

Хеширование

Хеширование в информатике — это процесс отображения произвольно большого набора данных $n$ в $m$ значений фиксированного размера. Это имеет применение в кэшировании , посредством которого большие наборы данных могут храниться путем ссылки на их репрезентативные значения (их «хеш-коды») в «хеш-таблице» для быстрого вызова. Обычно количество уникальных объектов в наборе данных $n$ больше, чем количество доступных уникальных хеш-кодов $m$ , и принцип «ящика» в этом случае гласит, что хеширование этих объектов не гарантирует уникальности, поскольку если вы хешируете все объекты в наборе данных $n$ , некоторые объекты обязательно должны иметь один и тот же хеш-код.

Использование и применение

Этот принцип можно использовать для доказательства того, что любой алгоритм сжатия без потерь , при условии, что он делает некоторые входные данные меньше (как предполагает «сжатие»), также увеличит некоторые другие входные данные. В противном случае набор всех входных последовательностей до заданной длины $L$ можно было бы сопоставить с (гораздо) меньшим набором всех последовательностей длиной меньше $L$ без коллизий (потому что сжатие происходит без потерь), возможность, которую исключает принцип «пихонхола».

Значимой проблемой в математическом анализе является, для фиксированного иррационального числа $a$ , показать, что множество ⁠ ⁠ $\{[na]:n\in \mathbb {Z} \}$ дробных частей плотно в $[0, 1] .$ Обнаруживается , что нелегко явно найти целые числа $n, m$ такие, что где $e$ $> 0$ — малое положительное число, а $a$ — некоторое произвольное иррациональное число. Но если взять $M$ такое, что ⁠ ⁠ по принципу ящика должно быть такое, что $n$ $1$ $a$ и $n$ $2$ $a$ находятся в одном и том же целочисленном подразделении размера ⁠ ⁠ (существует только $M$ таких подразделений между последовательными целыми числами). В частности, можно найти $n$ $1$ $,$ $n$ $2$ такие, что $|на-м|<е,$ ${\tfrac {1}{M}}<e,$ $n_{1},n_{2}\in \{1,2,\ldots ,M+1\}$ ${\tfrac {1}{M}}$

n_{1}a\in \left(p+{\frac {k}{M}},\ p+{\frac {k+1}{M}}\right),\quad n_{2}a\in \left(q+{\frac {k}{M}},\ q+{\frac {k+1}{M}}\right),

для некоторых целых чисел $p, q$ и $k$ из ${0, 1, ..., M - 1$ }. Тогда можно легко проверить, что

(n_{2}-n_{1})a\in \left(q-p-{\frac {1}{M}},q-p+{\frac {1}{M}}\right).

Это подразумевает, что ⁠ ⁠ $[na]<{\tfrac {1}{M}}<e,$ где $n = n 2 - n 1$ или $n = n 1 - n 2$ . Это показывает, что 0 является предельной точкой {[ $na$ ]}. Затем можно использовать этот факт для доказательства случая для $p$ в $(0, 1]$ : найти $n$ такое, что ⁠ ⁠ $[na]<{\tfrac {1}{M}}<e;$ тогда, если ⁠ ⁠ $p\in {\bigl (}0,{\tfrac {1}{M}}{\bigr ]},$ доказательство завершено. В противном случае

p\in \left({\frac {j}{M}},{\frac {j+1}{M}}\right],

и установив

k=\sup \left\{r\in N:r[na]<{\frac {j}{M}}\right\},

один получает

{\Bigl |}{\bigl [}(k+1)na{\bigr ]}-p{\Bigr |}<{\frac {1}{M}}<e.

Варианты встречаются в ряде доказательств. В доказательстве леммы о накачке для регулярных языков используется версия, которая смешивает конечные и бесконечные множества: если бесконечно много объектов помещаются в конечное количество коробок, то два объекта делят коробку. ^[18] В решении Фиска для проблемы Художественной галереи используется своего рода обратная формула: если $n$ объектов помещаются в $k$ коробок, то существует коробка, содержащая не более ⁠ ⁠ ${\tfrac {n}{k}}$ объектов. ^[19]

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

Ниже приведены альтернативные формулировки принципа «ящика».

Если $n$ объектов распределены по $m$ местам, и если $n > m$ , то некоторое место получает по крайней мере два объекта. ^[1]
(эквивалентная формулировка 1) Если $n$ объектов распределены по $n$ местам таким образом, что ни одно место не получает более одного объекта, то каждое место получает ровно один объект. ^[1]
(обобщение 1) Если $S$ и $T$ — множества, и $мощность$ S больше мощности $T$ , то не существует инъективной функции из $S$ в $T.$
Если $n$ объектов распределены по $m$ местам, и если $n < m$ , то в какое-то место не попадает ни одного объекта.
(эквивалентная формулировка 4) Если $n$ объектов распределены по $n$ местам таким образом, что ни одно место не получает ни одного объекта, то каждое место получает ровно один объект. ^[20]
(обобщение 4) Если $S$ и $T$ — множества, а мощность $S$ меньше мощности $T$ , то не существует сюръективной функции из $S$ в $T.$

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

Пусть $q 1, q 2, ..., q n$ — положительные целые числа. Если

q_{1}+q_{2}+\cdots +q_{n}-n+1

объекты распределены по $n$ ящикам, тогда либо первый ящик содержит не менее $q 1$ объектов, либо второй ящик содержит не менее $q 2$ объектов, ..., либо $n$ -й ящик содержит не менее $q n$ объектов. ^[21]

Простая форма получается из этого, если взять $q 1 = q 2 = ... = q n = 2$ , что дает $n + 1$ объектов. Взятие $q 1 = q 2 = ... = q n = r$ дает более количественную версию принципа, а именно:

Пусть $n$ и $r$ будут положительными целыми числами. Если $n (r - 1) + 1$ объектов распределены по $n$ коробкам, то по крайней мере одна из коробок содержит $r$ или более объектов. ^[22]

Это также можно сформулировать так: если $k$ дискретных объектов должны быть распределены по $n$ контейнерам, то по крайней мере один контейнер должен содержать по крайней мере объекты, где — функция потолка , обозначающая наименьшее целое число, большее или равное $x$ . Аналогично, по крайней мере один контейнер должен содержать не более объектов, где — функция пола , обозначающая наибольшее целое число, меньшее или равное $x$ . $\lceil k/n\rceil$ $\lceil x\rceil$ $\lfloor k/n\rfloor$ $\lfloor x\rfloor$

Обобщения принципа «ящика»

Вероятностное обобщение принципа ящиков гласит, что если $n$ голубей случайным образом поместить в $m$ ящиков с равномерной вероятностью $1/ m$ , то по крайней мере в одном ящике будет находиться более одного голубя с вероятностью

1-{\frac {(m)_{n}}{m^{n}}},

где $(m) n$ — падающий факториал $m (m - 1)(m - 2)...(m - n + 1)$ . Для $n = 0$ и для $n = 1$ (и $m > 0$ ) эта вероятность равна нулю; другими словами, если есть только один голубь, конфликта быть не может. Для $n > m$ (голубей больше, чем ячеек) это единица, и в этом случае это совпадает с обычным принципом ячеек. Но даже если количество голубей не превышает количества ячеек ( $n \leq 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 и так далее.

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

Однако этот принцип не является обобщением принципа Pigeonhole для конечных множеств: он в общем случае ложен для конечных множеств. Технически он гласит, что если $A$ и $B$ — конечные множества, такие что любая сюръективная функция из $A$ в $B$ не является инъективной, то существует элемент $b$ из $B,$ такой что существует биекция между прообразом $b$ и $A.$ Это совсем другое утверждение, и оно абсурдно для больших конечных мощностей.

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

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

Смотрите также

Примечания

^ abc Herstein 1964, стр. 90
^ abc Rittaud, Benoît; Heeffer, Albrecht (2014). «Принцип пигмея, за два столетия до Дирихле». The Mathematical Intelligencer . 36 (2): 27–29. doi :10.1007/s00283-013-9389-1. hdl : 1854/LU-4115264 . MR 3207654. S2CID 44193229.
^ Джефф Миллер, Питер Флор, Гуннар Берг и Хулио Гонсалес Кабильон. "Принцип Пигеонхола". В Jeff Miller (ред.) Earlyiest Known Uses of Some of the Words of Mathematics . Электронный документ, получен 11 ноября 2006 г.
^ Флетчер и Патти 1987, стр. 27
^ Циммерманн, Карл-Хайнц (2006). Дискретная математика. Книги по запросу. п. 367. ИСБН 9783833455292.
^ Вайнтрауб, Стивен Х. (17 мая 2017 г.). Книга посвящения. Courier Dover Publications. стр. 13. ISBN 9780486811994.
↑ Джеймс, RC (31 июля 1992 г.). Математический словарь. Springer. стр. 490. ISBN 9780412990410.
^ Пандей, Авинаш. "D3 Graph Theory - Интерактивные учебники по теории графов". d3gt.com . Получено 12.01.2021 .
^ Риньяно, Эудженио (1923). Психология рассуждения. Перевод Холл, Уинифред АК Пол, Trench, Trubner & Company, Limited. стр. 72. ISBN 9780415191326.
^ Чтобы избежать некоторой запутанности изложения, этот пример относится только к людям, которые не являются лысыми.
^ «Население Лондона / Администрация Большого Лондона (GLA)». data.london.gov.uk .
^ «Дополнение к Афинскому Оракулу: Собрание оставшихся вопросов и ответов в старом Афинском Меркурии. ... К которому предпослана История Афинского Общества, ... написанная членом Афинского Общества». 1710.
^ «Афинский Оракул представляет собой полное собрание всех ценных вопросов и ответов». 1704.
^ «Афинский оракул: полное собрание всех ценных вопросов и ответов в старых афинских Меркуриях. ... Членом Афинского общества». 1704.
^ Лерешон, Жан (1622), Selecæe Propositiones in Tota Sparsim Mathematica Pulcherrimæ , Гаспарем Бернардум, стр. 2
^ Гримальди 1994, стр. 277
^ Гарднер, Мартин (октябрь 1976 г.). «Комбинаторные задачи, некоторые старые, некоторые новые и все недавно решенные компьютером». Математические игры. Scientific American . Т. 235, № 4. С. 131–137. JSTOR 24950467.
^ Введение в формальные языки и автоматы , Питер Линц, стр. 115–116, Jones and Bartlett Learning, 2006
^ Вычислительная геометрия на языке C , Кембриджские трактаты по теоретической информатике, 2-е издание, Джозеф О'Рурк, стр. 9.
^ Бруальди 2010, стр. 70
^ Бруальди 2010, с. 74 Теорема 3.2.1.
^ В вводной части это было представлено с заменами $m = n$ и $k = r - 1$ .
^ Ааронов, Якир; Коломбо, Фабрицио; Попеску, Санду; Сабадини, Ирен ; Струппа, Даниэле К.; Толлаксен, Джефф (2016). «Квантовое нарушение принципа дирижабля и природа квантовых корреляций». Труды Национальной академии наук . 113 (3): 532–535. Bibcode : 2016PNAS..113..532A. doi : 10.1073/pnas.1522411112 . PMC 4725468. PMID 26729862 .
^ «Квантовые ячейки вовсе не парадоксальны, говорят физики». 8 января 2015 г.
^ Рэй, Аластер; Форган, Тед (2014-12-03). «О последствиях эффекта квантового Дирихле». arXiv : 1412.1333 [quant-ph].

Ссылки

Бруальди, Ричард А. (2010), Введение в комбинаторику (5-е изд.), Pentice Hall, ISBN 978-0-13-602040-0
Флетчер, Питер; Патти, К. Уэйн (1987), Основы высшей математики , PWS-Kent, ISBN 978-0-87150-164-6
Гримальди, Ральф П. (1994), Дискретная и комбинаторная математика: прикладное введение (3-е изд.), Addison-Wesley, ISBN 978-0-201-54983-6
Херштейн, IN (1964), Топики по алгебре , Уолтем: Blaisdell Publishing Company, ISBN 978-1114541016

Внешние ссылки

Послушайте эту статью ( 24 минуты )

Этот аудиофайл был создан на основе редакции этой статьи от 5 июня 2021 года и не отражает последующие правки.

«Принцип ящика Дирихле», Энциклопедия математики , EMS Press , 2001 [1994]
«Странный случай принципа Дирихле»; Эдсгер Дейкстра исследует интерпретации и переформулировки принципа.
«Принцип Дирихле»; элементарные примеры принципа, используемые Ларри Кьюсиком.
«Принцип Дирихле из сборника интерактивной математики и головоломок»; базовый анализ принципа Дирихле и примеры Александра Богомольного .
«16 забавных применений принципа ящика»; Интересные факты, полученные с помощью этого принципа.
«У скольких людей одинаковое количество волос на теле?». Серия PBS Infinite . 1 декабря 2016 г. Архивировано из оригинала 2021-12-11 – через YouTube .