При́нцип Діріхле́ (також принцип коробок Діріхле, принцип голубів і кліток) — комбінаторне твердження, сформульоване німецьким математиком Петером Діріхле.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODFMelZqTDFSdmIwMWhibmxRYVdkbGIyNXpMbXB3Wnk4eU1qQndlQzFVYjI5TllXNTVVR2xuWlc5dWN5NXFjR2M9LmpwZw==.jpg)
Формулювання
Найчастіше в українськомовній і російськомовній літературі використовується неформальне формулювання з кролями і клітками. В англомовній літературі частіше у формулюванні присутні голуби (звідси поширена назва pigeonhole principle).
Найпоширеніше наступне формулювання цього принципу:
Припустимо, деяке число кроликів розсаджені в клітках. Якщо число кроликів більше, ніж число кліток, то хоч би в одній з кліток буде більше одного кролика.
Загальніше формулювання:
Припустимо, m кроликів розсаджені в n клітках. Тоді хоч би в одній клітці міститься не менше
кроликів, а також хоч би в одній іншій клітці міститься не більше
кроликів.
У рамках більш абстрактних понять:
Нехай задана функція
і потужність множини
більше потужності
. Тоді функція
не є ін'єктивною.
Нехай задана функція
на скінченних множинах і потужність множини
, де
. Тоді існує
в який відображається не менше n+1-го
.
Можливі також формулювання для окремих випадків, наприклад:
Якщо число кліток більше, ніж число кролів, то принаймні одна клітка порожня.
Альтернативні формулювання
Також є такі альтернативні формулювання принципу Діріхле.
- Якщо 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 друзів: C210 = 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, згідно з принципом Діріхле серед чисел n1, n2 ∈ {1, 2, ..., M + 1} такі, що n1a та n2a існують такі два 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)a належить (q − p − 1/M, q − p + 1/M). Тобто [na] < 1/M < e, де n = n2 − n1 або n = n1 − n2. Тобто 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 = n2 − n1 або n = n1 − n2. Це показує, що 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, то щонайменше, один закуток матиме більше одного голуба з ймовірністю
де (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
- Fletcher, Peter; Patty, C.Wayne (1987), Foundations of Higher Mathematics, PWS-Kent, ISBN
- (1994), Discrete and Combinatorial Mathematics: An Applied Introduction (вид. 3rd), ISBN
- Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет