Dirihlē princips

Vikipēdijas lapa
Pārlēkt uz: navigācija, meklēt
Šajā attēlā redzami n = 10 baloži m = 9 būros. Tā kā skaitlis 10 ir lielāks nekā 9, Dirihlē princips norāda, ka vismaz vienā būrī būs 2 baloži.

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.[1] Šī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ē atviltņu principu[2] — Nosaukums "Atviktņ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.[3] 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), tomēr to izmanto arī bezgalīgām kopām.

Piemēri[labot šo sadaļu | labot pirmkodu]

Zeķu izvēlēšanās[labot šo sadaļu | labot pirmkodu]

Iedomājieties, ka jums ir vairākas melnas un zilas zeķes, kāds ir minimālais skaits zeķu, 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 vismaz vienu pāri ar vienādas krāsas zeķēm m = 2 , jums vajag tikai 3 zeķes n = 3.

Roku paspiešana[labot šo sadaļu | labot pirmkodu]

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[labot šo sadaļu | labot pirmkodu]

Mēs varam pierādīt, ka Londonā ir vismaz divi cilvēki, kuriem ir vienāds skaits matu uz galvas.[4] 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[labot šo sadaļu | labot pirmkodu]

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 "paradoks" 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.

Softbola komanda[labot šo sadaļu | labot pirmkodu]

Iedomājieties 7 cilvēkus, kuri vēlas spēlēt Softbolu (n = 7), vienīgi viņi drīkst sadalīties tikai 4 komandās (m = 4). Dirihlē princips norāda, ka katrs nevar spēlēt savā komandā, bet vismaz 2 cilvēkiem būs jāspēlē vienā:

Citi formulējumi[labot šo sadaļu | labot pirmkodu]

Šie ir citi Dirihlē principa formulējumi.

  1. Ja n priekšmeti tiek ievietoti m vietās, un ja n > m, tad kādā vietā būs vismaz divi objekti.[1]
  2. (līdzīgs formulējums kā 1.) Ja n priekšmeti tiek ievietoti n vietās tā, ka nevienā vietā nav vairāk kā viens priekšmets, tad katra vieta saņem tieši vienu priekšmetu.[1]
  3. Ja n priekšmeti tiek ievietoti m vietās, un ja n < m, tad kādā vietā nebūs neviens priekšmets.
  4. (līdzīgs formulējums kā 3) Ja n priekšmeti tiek ievietoti n vietās tā, lai katrā vietā būtu kāds priekšmets, tad katrā vietā būs tieši viens objekts.[5]

Vispārīgā forma[labot šo sadaļu | labot pirmkodu]

q1, q2, …, qn ir pozitīvi veseli skaitļi. Ja

priekšmeti tiek ievietoti n kastītēs, tad vai nu pirmā kastīte satur vismaz q1 priekšmetus, vai otrā kastīte satur vismaz q2 priekšmetus, …, vai ntā kastīte satur vismaz qn priekšmetus.[6]

Vienkāršā forma ir iegūta no šīs ņemot q1 = q2 = … = qn = 2, kas dod n + 1 priekšmetus. Ņemot q1 = q2 = … = qn = r tiek iegūta plašāka versija par Dirihlē principu:

n un r ir pozitīvi veseli skaitļi. Ja n(r – 1) + 1 priekšmeti tiek ievietoti n kastēs, tad vismaz viena no kastēm satur r vai vairāk priekšmetus.[7]

Tas var tikt formulēts arī kā, ja k atsevisķi objekti tiek ievietoti n konteineros, tad vismaz vienam konteineram ir jāsatur vismaz objekti, kur ir griestu funkcija, norādot, ka mazākais veselais skaitlis ir lielāks vai vienāds ar x. Līdzīgi, vismaz vienam konteineram ir jāsatur ne vairāk kā objektu, kur ir grīdas funkcija, norādot, ka lielākais veselais skaitlis ir mazāks vai vienāds ar x.

Dirihlē principa vispārinājumi[labot šo sadaļu | labot pirmkodu]

Varbūtības vispārinājums Dirihlē principam norāda, ka ja n baloži tiek nejauši ievietoti m būros ar varbūtību 1/m, tad vismaz viens būris saturēs vairāk nekā vienu balodi ar iespējamību

kur (m)n ir dilstošs faktoriāls m(m − 1)(m − 2)...(mn + 1). Ja n = 0 un n = 1 (un m > 0), tad varbūtība ir 0; citiem vārdiem sakot, ja ir tikai viens balodis, tad nevar būt pretruna. Ja n > m (baložu vairāk par būriem) varbūtība ir 1, un tādā gadījumā tas sakrīt ar ierasto Dirihlē principu. Bet pat ja baložu skaits nepārsniedz būru skaitu (nm), sakarā ar to, ka baloži tiek ievietoti pēc nejaušības principa, bieži vien ir iespēja, ka radīsies sadursmes. Piemēram, ja 2 baloži tiek nejauši ievietoti 4 būros, ir 25% iespējamība, ka vismaz 1 būris saturēs vairāk nekā 1 balodi; 5 baložiem un 10 būriem šī iespējamība ir 69.76%; un 10 baložiem un 20 būriem apmēram 93.45%. Ja būru skaits netiek mainīts, iespējamība vienmēr augs, ja jūs palielināsiet baložu skaitu. Šī problēma tiek plašāk apskatīta "Dzimšanas dienu paradoksā".

Bezgalīgas kopas[labot šo sadaļu | labot pirmkodu]

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.

Atsauces[labot šo sadaļu | labot pirmkodu]

  1. 1,0 1,1 1,2 Herstein 1964, p. 90
  2. Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Electronic document, retrieved November 11, 2006
  3. Fletcher & Patty 1987, p. 27
  4. Šajā gadījumā mēs pieņemsim, ka neviens cilvēks nav plikgalvains.
  5. Brualdi 2010, 70. lpp
  6. Brualdi 2010, 74 Theorem 3.2.1. lpp
  7. In the lead section this was presented with the substitutions m = n and k = r − 1.

Papildu literatūra[labot šo sadaļu | labot pirmkodu]

Ārējās saites[labot šo sadaļu | labot pirmkodu]