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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Зображення голубів у комірках. Тут n = 10 голубів у m = 9 комірках. Оскільки 10 більше ніж 9, принцип Діріхле каже, що щонайменше одна комірка міститиме більш ніж одного голуба

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

Формулювання[ред.ред. код]

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

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

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

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

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

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

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

Нехай задана функція на скінченних множинах і потужність множини , де . Тоді існує в який відображається не менше n+1-го .

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

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

Альтернативні формулювання[ред.ред. код]

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

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

Історія[ред.ред. код]

Перша формалізація ідеї, як вважають, була зроблена Діріхле в 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 існують такі два n1n2, що n1a належить (p + k/M, p + (k + 1)/M), і n2a належить (q + k/M, q + (k + 1)/M), для деяких цілих чисел pq і деякому k з {0, 1, ..., M − 1}. Легко перевірити, що (n2n1)a належить (qp − 1/M, qp + 1/M). Тобто [na] < 1/M < e, де n = n2 n1 або n = n1n2. Тобто 0 є граничною точкою множини {[na]}. З цього можна отримати твердження для довільного p з (0, 1]: нехай n таке що [na] < 1/M < e; тоді якщо p ∈ (0, 1/M], одержується твердження. В іншому випадку p з (j/M, (j + 1)/M], і взявши k = sup{rN : r{na} < j/M}, одержуємо |{(k + 1)na} − p| < 1/M < e.

Використання і додатки[ред.ред. код]

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

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

Помітною проблемою в математичному аналізі є, при фіксованому ірраціональному числі а, показати, що множина {[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/Mp + (k + 1)/M), і n2a в (q + k / Mq + (k + 1)/M) для деякого p, q цілих і k в {0, 1, ..., M - 1}. Тепер ми можемо легко перевірити, що (n2 - n1)а в (q − p − 1/Mq − p + 1/M). Це означає, що [] < 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 такий самий, як не існує ін'єкційного відображення від А до В. Однак додавання, щонайменше, одиного елемента кінцевої безлічі є достатнім для того, щоб потужність збільшувалася.

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

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

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

Квантова механіка[ред.ред. код]

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

Література[ред.ред. код]

  • Ядренко М.Й. Принцип Діріхле.– Х.: Основа, 2005.– 96с.
  • Ричард Бруальди (2010), Введення до Комбінаторики (5-те вид.), Prentice Hall, ISBN 978-0-13-602040-0
  • Пітер Флетчер; Патті, C.Вейн (1987), Основи вищої математики, PWS-Кент, ISBN 0-87150-164-3
  • Ральф Грімальді (1994), Дискретна і комбінаторна математики: Прикладне Введення (3-те вид.), ISBN 978-0-201-54983-6
  • Херстейн (1964), Теми в алгебрі, Уолтем: Blaisdell Publishing Company, ISBN 978-1114541016