Принцип Діріхле

При́нцип Діріхле́ (також принцип коробок Діріхле, принцип голубів і кліток) — комбінаторне твердження, сформульоване німецьким математиком Петером Діріхле.

Формулювання

Найчастіше в українськомовній і російськомовній літературі використовується неформальне формулювання з кролями і клітками. В англомовній літературі частіше у формулюванні присутні голуби (звідси поширена назва pigeonhole principle).

Найпоширеніше наступне формулювання цього принципу:

Припустимо, деяке число кроликів розсаджені в клітках. Якщо число кроликів більше, ніж число кліток, то хоч би в одній з кліток буде більше одного кролика.

Загальніше формулювання:

Припустимо, m кроликів розсаджені в n клітках. Тоді хоч би в одній клітці міститься не менше $\lceil m/n\rceil$ кроликів, а також хоч би в одній іншій клітці міститься не більше $\lfloor m/n\rfloor$ кроликів.

У рамках більш абстрактних понять:

Нехай задана функція $f:A\rightarrow B$ і потужність множини $A$ більше потужності $B$ . Тоді функція $f$ не є ін'єктивною.

Нехай задана функція $f:A\rightarrow B$ на скінченних множинах і потужність множини $|A|>n|B|$ , де $n\in \mathbb {N}$ . Тоді існує $y\in B$ в який відображається не менше n+1-го $x_{1},x_{2},\dots ,x_{n+1}\in A$ .

Можливі також формулювання для окремих випадків, наприклад:

Якщо число кліток більше, ніж число кролів, то принаймні одна клітка порожня.

Альтернативні формулювання

Також є такі альтернативні формулювання принципу Діріхле.

Якщо n об'єктів розподілені по m місцях та якщо n > m, то якесь місце отримує принаймні два об'єкти.
(еквівалентне формулювання 1) Якщо n об'єктів розподілені по m місцях таким чином, що на жодному місці не має більше одного об'єкта, то кожне місце отримує рівно один об'єкт.
Якщо n об'єктів розподілені по m місцях та якщо n < m, то на якомусь місці немає об'єкта.
(еквівалентне формулювання 3) Якщо n об'єктів розподілені по n місцях таким чином, що немає місця, яке б не отримало об'єкт, то кожне місце має рівно один об'єкт.

Історія

Перша формалізація ідеї, як вважають, була зроблена Діріхле в 1834 році під назвою Schubfachprinzip («принцип шухляди» або «принцип полку»). З цієї причини він також зазвичай званий принципом коробки Дірихле, принципом ящика Діріхле або просто принципом Дірихле — ім'я, яке може також ставитися до принципу мінімуму для гармонійних функцій. Оригінальна назва «шухляда» до сих пір використовується у французькій мові («principe des tiroirs»).

Принцип має кілька узагальнень і може бути виражена різними способами. Зокрема, для натуральних чисел k та m, якщо n = km + 1 об'єкти розподілені серед m множин, то принцип Діріхле стверджує, що принаймні одна з множин буде містити щонайменше, до k + 1 об'єктів. Для довільного n і m це узагальнююче до k + 1 = ⌊ (n — 1) / m⌋ + 1, де ⌊ … ⌋ функція взяття цілої частини від виразу (n — 1) / m.

Приклади застосування

10 друзів відправили один одному святкові листівки. Кожний із них відправив 5 листівок. Довести, що якихось двоє друзів відправили листівки один одному.

Доведення: кількість пар, що можна утворити з 10 друзів: C²₁₀ = 45. А всього відправлених листівок 5∙10=50. Отже, згідно з принципом Діріхле, на деякі з пар друзів припадає дві листівки.

Картки пронумеровані послідовно цілими числа ми від 1 до 2n +1. Яку найбільшу кількість карток можна вибрати так, щоб жоден з номерів не дорівнював сумі якихось двох інших номерів карток?

Розв'язання. Припустімо, що таких карток існує не менше ніж n+2. Розташуємо вибрані картки в порядку зростання їхніх номерів, віднімемо від усіх номерів найменший номер картки. Одержується n + 1 різних чисел, відмінних від 0. Тоді, згідно з принципом Діріхле, отримана множина має принаймні один спільний елемент із початковою. Це число відповідно буде сумою двох чисел. Легко перевірити, що для n + 1 картки з непарними номерами {1,3,5,…, 2n +1} умови задачі вже виконуються.

З використанням принципу Діріхле можна довести, що для довільного ірраціонального a, множина {[na]: n ціле число} дробових частин є щільною в [0, 1]. Взявши M таке що 1/M < e, згідно з принципом Діріхле серед чисел n₁, n₂ ∈ {1, 2, ..., M + 1} такі, що n₁a та n₂a існують такі два n₁, n₂, що n₁a належить (p + k/M, p + (k + 1)/M), і n₂a належить (q + k/M, q + (k + 1)/M), для деяких цілих чисел p, q і деякому k з {0, 1, ..., M − 1}. Легко перевірити, що (n₂ − n₁)a належить (q − p − 1/M, q − p + 1/M). Тобто [na] < 1/M < e, де n = n₂ − n₁ або n = n₁ − n₂. Тобто 0 є граничною точкою множини {[na]}. З цього можна отримати твердження для довільного p з (0, 1]: нехай n таке що [na] < 1/M < e; тоді якщо p ∈ (0, 1/M], одержується твердження. В іншому випадку p з (j/M, (j + 1)/M], і взявши k = sup{r ∈ N : r{na} < j/M}, одержуємо |{(k + 1)na} − p| < 1/M < e.

Використання і додатки

Принцип Діріхле застосовується в інформатиці. Наприклад, однакові елементи завжди можуть бути в геш-таблиці, так як число можливих ключів перевищує число індексів в масиві. Алгоритм геш-функції, незалежно від того, як він працює, не може уникнути однакових значень індексів.

Ще одним наслідком принципу є те, для будь-якого алгоритму стиснення без втрат, знайдеться файл, який не може бути стисненний. В іншому випадку, множина всіх вхідних послідовностей до заданої довжини L може бути відображена в (набагато) меншу множину всіх послідовностей довжини менше L без збігів (так як стиснення без втрат), що неможливо відповідно до принципу Діріхле.

Помітною проблемою в математичному аналізі є те, що при фіксованому ірраціональному числі а, можна показати, що множина {[na]: n — це ціле число} дробова частина щільно розташована на проміжку [0, 1]. Дехто вважає, що не так легко знайти в явному вигляді цілих чисел n, m, що | na − ma | < e, де e > 0 є мале позитивне число та а деяке довільне ірраціональне число. Але якщо взяти М, що 1 / М < е, за принципом Діріхле має бути n1, n2 ∈ {1, 2, …, М + 1}, що n1a і n2a знаходяться в тому ж самому цілочисельному підрозділі розміру 1 / M (є тільки М такі підрозділи між послідовними цілими числами). Зокрема, ми можемо знайти n1, n2 такі, що n1a в (p + k/M, p + (k + 1)/M), і n2a в (q + k / M, q + (k + 1)/M) для деякого p, q цілих і k в {0, 1, …, M — 1}. Тепер ми можемо легко перевірити, що (n2 — n1)а в (q − p − 1/M, q − p + 1/M). Це означає, що [nа] < 1 / М < е, де n = n₂ − n₁ або n = n₁ − n₂. Це показує, що 0 є граничною точкою {[na]}. Потім ми можемо використовувати цей факт, щоб довести випадок для р в (0, 1]: знайти n таке, що [na] < 1 / М < е; тоді, якщо р ∈ (0, 1 / M], ми зробили. В іншому випадку р ∈ ((j / M, (j + 1)/M], і шляхом встановлення k = sup{r ∈ N : r[na] < j/M}, отримуємо |[(k + 1)na] − p| < 1/M < e.

Узагальнення принципу Діріхле

Вірогідне узагальнення принципу Діріхле констатує, що якщо 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 ≤ 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.

Нескінченні множини

Принцип Діріхле може бути розширений до нескінченних множин, формулюючи його в термінах кардинальних чисел: якщо потужність множини А більше потужності множини В, то немає ін'єктивності від А до B. Однак, в такій формі принцип тавтологічний, так як сенс твердження, що потужність множини А більше потужності множини B такий самий, як не існує ін'єкційного відображення від А до В. Однак додавання, щонайменше, одиного елемента скінченної множини є достатнім для того, щоб потужність збільшувалася.

Інший спосіб вираження принцип Діріхле для скінченних множин аналогічний принципу, що скінченної множини є скінченними Дедекіндовими^[en] множинами: Нехай А і В скінченної множини. Якщо є сюр'єкція з А до В, але немає ін'єкції, то не сюр'єкція від А до В є ін'єкцією. Насправді жодна з функцій будь-якого роду від А до В не є ін'єктивною. Це не вірно для нескінченних множин: Розглянемо функцію на множині натуральних чисел, що відправляє 1 і 2 до 1, 3 і 4 до 2, 5 і 6 до 3, і так далі.

Існує аналогічний принцип для нескінченних множин: якщо незліченну множину голубів розставляють на скінченне число поличок, буде існувати принаймні одина поличка, що має незліченну множину голубів поставлених на неї.

Цей принцип не є узагальненням принципу Діріхле для скінченних множин, проте це, взагалі кажучи, невірно для скінченних множин. З технічної точки зору він говорить, що якщо А і В є скінченними множинами такими, що будь-яка сюр'єкція з А до В не є ін'єкцією, то існує елемент b із В такий, що існує взаємно однозначна відповідність між прообразом b і А. Це зовсім інше твердження, і беззмістовне для множин з великим кардинальним числом.

Квантова механіка

Якір Аараонов^[en] математично продемонстрував, як принцип Діріхле може бути порушений в квантовій механіці і запропонував інтерферометричні експерименти для перевірки принципу Діріхле в квантовій механіці.[1]

Див. також

Список об'єктів, названих на честь Діріхле

Література

Ядренко М. Й. Принцип Діріхле.– Х.: Основа, 2005.– 96с.
Чудаков Н. Г. Введение в теорию L-функций Дирихле.
Андреев А. А., Горелов Г. Н. и др. Принцип Дирихле.
Brualdi, Richard A. (2010), Introductory Combinatorics (вид. 5th), Pentice Hall, ISBN 978-0-13-602040-0
Fletcher, Peter; Patty, C.Wayne (1987), Foundations of Higher Mathematics, PWS-Kent, ISBN 0-87150-164-3
Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics: An Applied Introduction (вид. 3rd), ISBN 978-0-201-54983-6
Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016