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

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

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

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

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

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

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

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

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

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

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

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

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

• 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} such that n₁a and 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.

Література

• Ядренко М.Й. Принцип Діріхле.– Х.: Основа, 2005.– 96с.