Dirihlē princips

Matemātikā Dirihlē princips norāda, ka ja n priekšmetus ievieto m kastītēs, kur n > m, tad vismaz vienā kastītē atradīsies vairāk kā viens priekšmets. Šīs teorēmas piemēri ir sastopami arī reālajā dzīvē, piemēram, "no trīs cimdiem, vismaz divi būs labās rokas vai arī kreisās rokas cimdi". Lai arī tas šķiet intuitīvs apgalvojums, to var izmantot, lai parādītu iespējami negaidītus rezultātus, piemēram, ka vismaz diviem cilvēkiem Londonā uz galvas ir vienāds skaits matu.
Ir ticams, ka pirmo reizi šo ideju pauda Pēters Gustavs Ležēns Dirihlē 1834. gadā, ar nosaukumu Schubfachprinzip ("atviktņu princips" vai "plauktu princips"). Tas bieži tiek saukts arī par Baložu būru principu vai Dirihlē atvilktņu principu — Nosaukums "Atvilktņu princips" joprojām tiek lietots franču valodā ("principe des tiroirs"), poļu valodā ("zasada szufladkowa"), bulgāru valodā ("принцип на чекмеджетата"), turku valodā ("çekmece ilkesi"), ungāru valodā ("skatulyaelv"), itāļu valodā ("principio dei cassetti"), vācu valodā ("Schubfachprinzip"), dāņu valodā ("Skuffeprincippet"), un ķīniešu valodā ("抽屉原理").
Dirihlē princips var tikt skaidrots dažādi, tomēr visbiežāk to saprot šādi: ja k un m ir naturāli skaitļi , un n = km + 1 priekšmeti tiek ievietoti m kastēs, tad Dirihlē princips apgalvo, ka vismaz viena kaste saturēs vismaz k + 1 priekšmetus. Patvaļīgiem n un m tas vispārinas uz k + 1 = ⌊(n – 1)/m⌋ + 1, kur ⌊...⌋ ir grīdas funkcija.
Lai gan visbiežāk Dirihlē princips tiek lietots galīgām kopām (kā, piemēram, baloži un kastītes), to izmanto arī bezgalīgām kopām.

Zeķu izvēlēšanās

Iedomājieties, ka jums ir maiss ar bezgalīgi daudz oranžām un bezgalīgi daudz baltām zeķēm. Kāds ir minimālais skaits zeķu, kas jāizvelk no maisa, lai būtu garantēts, ka jums būs pāris ar vienādas krāsas zeķēm? Dirihlē princips norāda, ka, lai iegūtu vienu pāri ar vienādas krāsas zeķēm m = 2 , jums vajag tikai 3 zeķes n = 3.

Roku paspiešana

Ja ir n cilvēki, kuri var paspiest roku viens ar otru (kur n > 1), Dirihlē princips parāda, ka vienmēr ir divi cilvēki, kuri paspiedīs roku ar vienādu skaitu cilvēkiem. Tā kā m atbilst skaitam cik reizes tiek paspiestas rokas, un katrs cilvēks var paspiest roku ar ikvienu no 0 līdz n − 1 cilvēkiem, tas rada n − 1 "būrus". Tas ir tāpēc, ka gan '0', gan 'n − 1' "būrim" jābūt tukšam (ja viens cilvēks paspiež roku ar visiem, nav iespējams, ka ir cilvēks, kurš nebūtu paspiedis roku ne ar vienu; tāpat, ja viens cilvēks nepaspiež roku ne ar vienu, tad nevar būt cilvēks, kurš būtu paspiedis roku ar visiem). Pēc tā seko, ka n cilvēki tiek ielikti n − 1 "būros", kas garantē dubultošanos.

Matu skaitīšana

Mēs varam pierādīt, ka Londonā ir vismaz divi cilvēki, kuriem ir vienāds skaits matu uz galvas. Tā kā parasti cilvēkam uz galvas ir apmēram 150,000 matu; ir loģiski pieņemt, ka nevienam nav vairāk nekā 1,000,000 matu (m = 1 miljons būri). Londonā ir vairāk nekā 1,000,000 cilvēku (n ir vairāk nekā miljons priekšmetu). Piešķirot "būri" katram cilvēku matu skaitam, un piešķirot cilvēkus "būriem" atbilstoši viņu matu skaitam, līdz 1,000,001 piešķiršanai, ir jābūt vismaz diviem cilvēkiem, kuri ir piešķirti vienam un tam pašam "būrim" (jo viņiem ir vienāds skaits matu uz galvas) (vai, n > m). Tā kā cilvēkam ir vidēji (m = 150 000) matu, tad katrā "būrī" būs vismaz viens cilvēks, un 150,001 cilvēks būs "būrī", kurā kāds jau ir. Ir iespējams, ka pārklāšanās notiks jau ātrāk nekā 150 001. reizē — svarīgākais ir tas, ka tā vispār notiks. Dirihlē princips nenorāda skaitu, cik reizes notiek pārklāšanās (par to stāsta varbūtību teorija).

Dzimšanas dienas problēma

Dzimšanas dienas problēma vaicā, kāda ir iespējamība, ka nejauši izvēlētu n cilvēku grupā, diviem cilvēkiem dzimšanas diena būs vienā un tajā pašā dienā? Pēc Dirihlē principa, ja istabā ir 367 cilvēku, mēs zinām, ka ir vismaz viens pāris, kuri dzimuši vienā dienā, jo ir tikai 366 iespējamas dzimšanas dienas no kurām izvēlēties (ieskaitot 29. februāri). Dzimšanas dienu "paradokss" noved pie tā, ka pat grupā, kurā ir tikai 23 cilvēki, ir 50% iespējamība, ka būs divi cilvēki ar vienu dzimšanas dienu. Lai gan pirmajā brīdī tas var šķist pārsteidzoši, šķiet loģiski, ka salīdzināšana notiks starp jebkuriem diviem cilvēkiem, nevis starp vienu cilvēku un visu grupu.

Bezgalīgas kopas

Bezgalīgām kopām ir līdzīgs princips: Ja nesaskaitāmi daudz baložu tiek ievietoti saskaitāmi daudz būros, tad eksistē vismaz viens būris, kurā ir nesaskaitāmi daudz baložu.