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

Уикипедия жобасынан алынған мәлімет
Мұнда ауысу: шарлау, іздеу
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 санынан аспайтындай қоян отырады.

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

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

Жалпылама[өңдеу]

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

Әдебиет[өңдеу]