Dirihlē princips

Matemātikā Dirihlē princips norāda, ka ja  priekšmetus ievieto  kastītēs, kur , 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  un  ir naturāli skaitļi , un  priekšmeti tiek ievietoti  kastēs, tad Dirihlē princips apgalvo, ka vismaz viena kaste saturēs vismaz  priekšmetus. Patvaļīgiem  un  tas vispārinas uz , 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.

Piemēri

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  , jums vajag tikai 3 zeķes .

Roku paspiešana 
Ja ir  cilvēki, kuri var paspiest roku viens ar otru (kur ), Dirihlē princips parāda, ka vienmēr ir divi cilvēki, kuri paspiedīs roku ar vienādu skaitu cilvēkiem. Tā kā  atbilst skaitam cik reizes tiek paspiestas rokas, un katrs cilvēks var paspiest roku ar ikvienu no 0 līdz  cilvēkiem, tas rada  "būrus". Tas ir tāpēc, ka gan '0', gan  "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  cilvēki tiek ielikti  "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  būri). Londonā ir vairāk nekā 1,000,000 cilvēku ( 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, ). Tā kā cilvēkam ir vidēji () 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  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.

Softbola komanda 
Iedomājieties 7 cilvēkus, kuri vēlas spēlēt Softbolu ), vienīgi viņi drīkst sadalīties tikai 4 komandās ). 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 
Šie ir citi Dirihlē principa formulējumi.

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

Vispārīgā forma 
 ir pozitīvi veseli skaitļi. Ja
 
priekšmeti tiek ievietoti  kastītēs, tad vai nu pirmā kastīte satur vismaz  priekšmetus, vai otrā kastīte satur vismaz  priekšmetus, …, vai tā kastīte satur vismaz  priekšmetus.

Vienkāršā forma ir iegūta no šīs ņemot , kas dod  priekšmetus. Ņemot  tiek iegūta plašāka versija par Dirihlē principu:

 un  ir pozitīvi veseli skaitļi. Ja  priekšmeti tiek ievietoti  kastēs, tad vismaz viena no kastēm satur  vai vairāk priekšmetus.

Tas var tikt formulēts arī kā, ja  atsevisķi objekti tiek ievietoti  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 .
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 .

Dirihlē principa vispārinājumi 

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

 

kur  ir dilstošs faktoriāls . Ja  un  (un ), tad varbūtība ir 0; citiem vārdiem sakot, ja ir tikai viens balodis, tad nevar būt pretruna. Ja  (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 (), 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 

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

Papildu literatūra

Ārējās saites 
 "The strange case of The Pigeon-hole Principle"; Dirihlē principa interpretācijas un formulējumi.
 "The Pigeon Hole Principle"; Elementāri Dirihlē principa piemēri.
 "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; Dirihlē principa analīze un piemēri.
 "16 fun applications of the pigeonhole principle"; Interesanti fakti.

Kombinatorika
Matemātikas principi