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

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

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

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

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

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

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

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

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

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

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

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

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

Приклади застосування[ред.ред. код]

  • 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} such that n1a and 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 = n2n1 або 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.

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

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