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

9 торда 7 кептер болса, Дирихле принципі бойынша кем дегенде 9-7=2 тор бос болады

9 торда 10 кептер болса, Дирихле принципі бойынша кемінде бір торда бірден артық кептер бар

Комбинаторикада Дирихле́ при́нципі (нем. Schubfachprinzip, «жәшіктер принципі») — заттар («қояндар») мен олар салынған контейнерлер («жәшіктер») арасындағы белгілі шарттар орындалғанда болатын байланыс туралы неміс математигі Дирихле 1834 жылы тұжырымдаған принцип. Ағылшын тілі мен кейбір басқа да тілдерде «кептерлер мен жәшіктер принципі» (ағылш. Pigeonhole principle) атымен белгілі.

Дирихле принципі, мысалы, диофанттық жақындау теориясында сызықтық теңсіздіктер жүйесін талдауда қолданылады.

Тұжырымдамалары

• Дирихле принципінің ең кең тараған тұжырымдамасы:

Егер қояндар торларға қояндар саны торлар санынан көп болатындай торларға отырғызылса, кем дегенде бір торда бір қояннан артық қоян болады.

• Жалпы түрі былай болады:

Егер m қоян n торға отырғызылса, онда кем дегенде бір торда кемінде $\left\lceil\frac{m}{n}\right\rceil$ қоян болады, ал кемінде бір торда $\left\lfloor\frac{m}{n}\right\rfloor$ санынан аспайтындай қоян отырады.

• Жекеше түрлері:

Егер торлар қояндарға қарағанда көбірек болса, онда кем дегенде бір тор бос болады.

• $f: A \rightarrow B$ функциясы A және B шекті жиындарда берілсін, $|A| > n|B|$, мұндағы $n \in \mathbb N$. Онда $f$ функциясы кейбір мәнін n+1 рет қабылдайды.

Жалпылама

Шексіз жиындар үшін де осы принциптің жалпыламасы бар: Жиын қуаттылығы көбіректің азырағына инъекция болмайды.

Әдебиет

• Үлгі қатесі: қара {{Кітап}}