Dirihlē princips

Šajā attēlā redzami Veidne:Nowrap baloži Veidne:Nowrap 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 Veidne:Math priekšmetus ievieto Veidne:Math kastītēs, kur Veidne:Math, 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 Veidne:Math un Veidne:Math ir naturāli skaitļi , un Veidne:Math priekšmeti tiek ievietoti Veidne:Math kastēs, tad Dirihlē princips apgalvo, ka vismaz viena kaste saturēs vismaz Veidne:Math priekšmetus. Patvaļīgiem Veidne:Math un Veidne:Math tas vispārinas uz Veidne:Math, kur Veidne:Math 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 Veidne:Math , jums vajag tikai 3 zeķes Veidne:Math.

Roku paspiešana

Ja ir Veidne:Math cilvēki, kuri var paspiest roku viens ar otru (kur Veidne:Math), Dirihlē princips parāda, ka vienmēr ir divi cilvēki, kuri paspiedīs roku ar vienādu skaitu cilvēkiem. Tā kā Veidne:Math atbilst skaitam cik reizes tiek paspiestas rokas, un katrs cilvēks var paspiest roku ar ikvienu no 0 līdz Veidne:Math cilvēkiem, tas rada Veidne:Math "būrus". Tas ir tāpēc, ka gan '0', gan Veidne:Math "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 Veidne:Math cilvēki tiek ielikti Veidne:Math "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 Veidne:Math būri). Londonā ir vairāk nekā 1,000,000 cilvēku (Veidne:Math 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, Veidne:Math). Tā kā cilvēkam ir vidēji (Veidne:Math) 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 Veidne:Math 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 Veidne:Math), vienīgi viņi drīkst sadalīties tikai 4 komandās Veidne:Math). Dirihlē princips norāda, ka katrs nevar spēlēt savā komandā, bet vismaz 2 cilvēkiem būs jāspēlē vienā:

$\lfloor \frac{(n-1)}{m}\rfloor +1=\lfloor \frac{(7-1)}{4}\rfloor +1=\lfloor \frac{6}{4}\rfloor +1=1+1=2$

Citi formulējumi

Šie ir citi Dirihlē principa formulējumi.

1. Ja Veidne:Math priekšmeti tiek ievietoti Veidne:Math vietās, un ja Veidne:Math, tad kādā vietā būs vismaz divi objekti.
2. (līdzīgs formulējums kā 1.) Ja Veidne:Math priekšmeti tiek ievietoti Veidne:Math vietās tā, ka nevienā vietā nav vairāk kā viens priekšmets, tad katra vieta saņem tieši vienu priekšmetu.
3. Ja Veidne:Math priekšmeti tiek ievietoti Veidne:Math vietās, un ja Veidne:Math, tad kādā vietā nebūs neviens priekšmets.
4. (līdzīgs formulējums kā 3) Ja Veidne:Math priekšmeti tiek ievietoti Veidne:Math 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

Veidne:Math ir pozitīvi veseli skaitļi. Ja

$q_1+q_2+\cdots +q_n-n+1$

priekšmeti tiek ievietoti Veidne:Math kastītēs, tad vai nu pirmā kastīte satur vismaz Veidne:Math priekšmetus, vai otrā kastīte satur vismaz Veidne:Math priekšmetus, …, vai Veidne:Mathtā kastīte satur vismaz Veidne:Math priekšmetus.

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

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

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

Dirihlē principa vispārinājumi

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

$1-\frac{(m{)}_n}{m^n},$

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

Papildu literatūra

• Veidne:Citation
• Veidne:Citation
• Veidne:Citation
• Veidne:Citation

Ā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.