9 клітин містять 7 голубів, за принципом Діріхле хоча б одна клітина містить не більше 7/9 голуба (т.е нуль)
9 клітин містять 10 голубів, за принципом Діріхле хоча б в одній клітині перебувають більше одного голуба

В комбінаториці принцип Діріхле ( ньому. Schubfachprinzip , "Принцип ящиків") - твердження, сформульоване німецьким математиком Діріхле в 1834, що встановлює зв'язок між об'єктами (" кроликами ") і контейнерами (" клітинами ") при виконанні певних умов. В англійською та деякими іншими мовами твердження відоме як "принцип голубів і ящиків" ( англ. Pigeonhole principle ), Коли об'єктами є голуби, а контейнерами - ящики.

Принцип Діріхле застосовується, зокрема, в теорії діофантових наближень при аналізі систем лінійних нерівностей.


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

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

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

  • Більш загальне формулювання звучить так:

Якщо m кроликів розсаджені в n клітин, то хоча б в одній клітині перебуває не менше \ Left \ lceil \ frac {m} {n} \ right \ rceil кроликів, а також хоча б в одній клітині перебуває не більше \ Left \ lfloor \ frac {m} {n} \ right \ rfloor кроликів.

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

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


Узагальнення

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

Література