Принцип «ячейки»

В математике принцип «ячейки» гласит, что если $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$ обозначают функции пола и потолка соответственно.

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

Этимология

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

Поскольку мебель с ячейками обычно используется для хранения или сортировки вещей по многим категориям (например, писем в почтовом отделении или ключей от номера в отеле), ячейка для перевода может быть лучшим воспроизведением оригинального «ящика» Дирихле. Понимание термина «голубятня» , относящегося к некоторым особенностям мебели, угасает – особенно среди тех, кто не говорит по-английски как на родном языке, а является лингва-франка в научном мире – в пользу более наглядной интерпретации, буквально включающей голубей и норы. Наводящая на размышления (хотя и не вводящая в заблуждение) интерпретация «голубятни» как « голубятни » недавно вернулась к немецкому обратному переводу «принципа голубятни» как « Taubenschlagprinzip ». ^[5]

Кроме оригинальных терминов « Shubfachprinzip » на немецком языке. ^[6] и « Principe des Tiroirs » на французском языке, ^[7] other literal translations are still in use in Arabic ( "مبدأ برج الحمام" ), Bulgarian (" принцип на чекмеджетата "), Chinese (" 抽屉原理 "), Danish (" Skuffeprincippet "), Dutch (" ladenprincipe "), Hungarian (" skatulyaelv "), Italian (" principio dei cassetti "), Japanese (" 引き出し論法 "), Persian (" اصل لانه کبوتری "), Polish (" zasada szufladkowa "), Portuguese (" Princípio das Gavetas "), Swedish (" Lådprincipen "), Turkish (" çekmece ilkesi "), and Vietnamese (" 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 года «Выбор предложений» : ^[2] «Необходимо, чтобы у двух мужчин было одинаковое количество волос, экю или других вещей, как друг у друга». ^[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, набора данных $n$ некоторые объекты обязательно должны иметь один и тот же хеш-код.

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

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

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

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,$ ⁠ где $п знак равно п 2 - п 1$ или $п знак равно п 1 - п 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 больше $S$ мощности $T$ , то не существует инъективной функции из $мощность$ в $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$ контейнерам, то хотя бы один контейнер должен содержать как минимум $\lceil k/n\rceil$ объекты, где $\lceil x\rceil$ — функция потолка , обозначающая наименьшее целое число, большее или равное $x$ . Аналогичным образом, по крайней мере, один контейнер должен вмещать не более $\lfloor k/n\rfloor$ объекты, где $\lfloor x\rfloor$ — это функция пола , обозначающая наибольшее целое число, меньшее или равное $x$ .

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

Вероятностное обобщение принципа ячеек гласит, что если $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$ не является инъективной. Это неверно для бесконечных множеств: рассмотрим функцию натуральных чисел, которая переводит 1 и 2 в 1, 3 и 4 в 2, 5 и 6 в 3 и так далее.

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

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

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

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

См. также

Примечания

^ Перейти обратно: ^а ^б ^с Херштейн 1964 , с. 90
^ Перейти обратно: ^а ^б ^с Ритто, Бенуа; Хеффер, Альбрехт (2014). «Принцип ячейки, за два столетия до Дирихле» . Математический интеллект . 36 (2): 27–29. дои : 10.1007/s00283-013-9389-1 . hdl : 1854/LU-4115264 . МР 3207654 . S2CID 44193229 .
^ Джефф Миллер, Питер Флор, Гуннар Берг и Хулио Гонсалес Кабильон. « Принцип ячейки ». В книге Джеффа Миллера (ред.) « Самые ранние известные варианты использования некоторых математических слов» . Электронный документ, получено 11 ноября 2006 г.
^ Флетчер и Пэтти 1987 , с. 27
^ Циммерманн, Карл-Хайнц (2006). Дискретная математика . п. 367. ИСБН 9783833455292 .
^ Вайнтрауб, Стивен Х. (17 мая 2017 г.). Книга индукции . п. 13. ISBN 9780486811994 .
^ Джеймс, RC (31 июля 1992 г.). Математический словарь . п. 490. ИСБН 9780412990410 .
^ Пандей, Авинаш. «Теория графов D3 — интерактивные учебные пособия по теории графов» . d3gt.com . Проверено 12 января 2021 г.
^ Риньяно, Эухенио (1923). Психология рассуждения . Перевод Холла, Уинифред А.К. Пол, Trench, Trubner & Company, Limited. п. 72. ИСБН 9780415191326 .
^ Чтобы избежать ненужной путаницы, этот пример относится только к не лысым людям.
^ «Население Лондона / Администрация Большого Лондона (GLA)» . data.london.gov.uk .
^ «Дополнение к Афинскому Оракулу: собрание оставшихся вопросов и ответов в Старых Афинских Меркуриях. ... К которому прилагается префикс «История Афинского общества... члена Афинского общества»» . 1710.
^ «Афинский оракул представляет собой целое собрание всех ценных вопросов и ответов» . 1704.
^ «Афинский оракул: полное собрание всех ценных вопросов и ответов в старых афинских Меркуриях. ... Член Афинского общества» . 1704.
^ Лерешон, Жан (1622), Selecæe Propositiones in Tota Sparsim Mathematica Pulcherrimæ , Gasparem Bernardum, p. 2
^ Гримальди 1994 , с. 277
^ Гарднер, Мартин (октябрь 1976 г.). «Комбинаторные задачи, некоторые старые, некоторые новые и все новые, атакованные компьютером». Математические игры. Научный американец . Том. 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. Бибкод : 2016PNAS..113..532A . дои : 10.1073/pnas.1522411112 . ПМЦ 4725468 . ПМИД 26729862 .
^ «Квантовые ячейки в конце концов не парадоксальны, — говорят физики» . 8 января 2015 г.
^ Рэй, Аластер; Форган, Тед (3 декабря 2014 г.). «О последствиях квантового эффекта голубя». arXiv : 1412.1333 [ квант-ph ].

Ссылки

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

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

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

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

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

[Herstein64-1] Перейти обратно: ^а ^б ^с Херштейн 1964 , с. 90

[leurechon-2] Перейти обратно: ^а ^б ^с Ритто, Бенуа; Хеффер, Альбрехт (2014). «Принцип ячейки, за два столетия до Дирихле» . Математический интеллект . 36 (2): 27–29. дои : 10.1007/s00283-013-9389-1 . hdl : 1854/LU-4115264 . МР 3207654 . S2CID 44193229 .

[3] Джефф Миллер, Питер Флор, Гуннар Берг и Хулио Гонсалес Кабильон. « Принцип ячейки ». В книге Джеффа Миллера (ред.) « Самые ранние известные варианты использования некоторых математических слов» . Электронный документ, получено 11 ноября 2006 г.

[4] Флетчер и Пэтти 1987 , с. 27

[5] Циммерманн, Карл-Хайнц (2006). Дискретная математика . п. 367. ИСБН 9783833455292 .

[6] Вайнтрауб, Стивен Х. (17 мая 2017 г.). Книга индукции . п. 13. ISBN 9780486811994 .

[7] Джеймс, RC (31 июля 1992 г.). Математический словарь . п. 490. ИСБН 9780412990410 .

[8] Пандей, Авинаш. «Теория графов D3 — интерактивные учебные пособия по теории графов» . d3gt.com . Проверено 12 января 2021 г.

[9] Риньяно, Эухенио (1923). Психология рассуждения . Перевод Холла, Уинифред А.К. Пол, Trench, Trubner & Company, Limited. п. 72. ИСБН 9780415191326 .

[10] Чтобы избежать ненужной путаницы, этот пример относится только к не лысым людям.

[11] «Население Лондона / Администрация Большого Лондона (GLA)» . data.london.gov.uk .

[12] «Дополнение к Афинскому Оракулу: собрание оставшихся вопросов и ответов в Старых Афинских Меркуриях. ... К которому прилагается префикс «История Афинского общества... члена Афинского общества»» . 1710.

[13] «Афинский оракул представляет собой целое собрание всех ценных вопросов и ответов» . 1704.

[14] «Афинский оракул: полное собрание всех ценных вопросов и ответов в старых афинских Меркуриях. ... Член Афинского общества» . 1704.

[15] Лерешон, Жан (1622), Selecæe Propositiones in Tota Sparsim Mathematica Pulcherrimæ , Gasparem Bernardum, p. 2

[16] Гримальди 1994 , с. 277

[17] Гарднер, Мартин (октябрь 1976 г.). «Комбинаторные задачи, некоторые старые, некоторые новые и все новые, атакованные компьютером». Математические игры. Научный американец . Том. 235, нет. 4. С. 131–137. JSTOR 24950467 .

[18] Введение в формальные языки и автоматы , Питер Линц, стр. 115–116, Jones and Bartlett Learning, 2006.

[19] Вычислительная геометрия на языке C , Кембриджские трактаты по теоретической информатике, 2-е издание, Джозеф О'Рурк, стр. 9.

[20] Бруальди 2010 , стр. 70.

[21] Бруальди 2010 , с. 74 Теорема 3.2.1.

[22] В начальном разделе это было представлено с заменами $m = n$ и $k = r - 1$ .

[23] Ааронов, Якир; Коломбо, Фабрицио; Попеску, Санду; Сабадини, Ирен ; Струппа, Даниэле К.; Толлаксен, Джефф (2016). «Квантовое нарушение принципа ячейки и природа квантовых корреляций» . Труды Национальной академии наук . 113 (3): 532–535. Бибкод : 2016PNAS..113..532A . дои : 10.1073/pnas.1522411112 . ПМЦ 4725468 . ПМИД 26729862 .

[24] «Квантовые ячейки в конце концов не парадоксальны, — говорят физики» . 8 января 2015 г.

[Rae_Forgan_2014-25] Рэй, Аластер; Форган, Тед (3 декабря 2014 г.). «О последствиях квантового эффекта голубя». arXiv : 1412.1333 [ квант-ph ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]