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.^[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ē atvilktņu principu^[2] — 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.^[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), 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 $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.^[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

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.

Softbola komanda

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ā:

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

Citi formulējumi

Šie ir citi Dirihlē principa formulējumi.

Ja $n$ priekšmeti tiek ievietoti $m$ vietās, un ja $n > m$ , tad kādā vietā būs vismaz divi objekti.^[1]
(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]
Ja $n$ priekšmeti tiek ievietoti $m$ vietās, un ja $n < m$ , tad kādā vietā nebūs neviens priekšmets.
(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

$q 1, q 2, \dots, q n$ ir pozitīvi veseli skaitļi. Ja

q_{1}+q_{2}+\cdots +q_{n}-n+1

priekšmeti tiek ievietoti $n$ kastītēs, tad vai nu pirmā kastīte satur vismaz $q 1$ priekšmetus, vai otrā kastīte satur vismaz $q 2$ priekšmetus, …, vai $n$ tā kastīte satur vismaz $q n$ priekšmetus.^[6]

Vienkāršā forma ir iegūta no šīs ņemot $q 1 = q 2 = \dots = q n = 2$ , kas dod $n + 1$ priekšmetus. Ņemot $q 1 = q 2 = \dots = q n = 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 $\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 $x$ . 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 $x$ .

Dirihlē principa vispārinājumi

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

1-{\frac {(m)_{n}}{m^{n}}},\!

kur $(m) n$ ir dilstošs faktoriāls $m (m - 1)(m - 2)...(m - n + 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 ( $n \leq m$ ), 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

↑ ^1,0 ^1,1 ^1,2 Herstein 1964, p. 90
↑ 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
↑ Fletcher & Patty 1987, p. 27
↑ Šajā gadījumā mēs pieņemsim, ka neviens cilvēks nav plikgalvains.
↑ Brualdi 2010, 70. lpp
↑ Brualdi 2010, 74 Theorem 3.2.1. lpp
↑ In the lead section this was presented with the substitutions $m = n$ and $k = r - 1$ .

Papildu literatūra

Brualdi, Richard A. (2010), Introductory Combinatorics (5th izd.), Pentice Hall, ISBN 978-0-13-602040-0
Fletcher, Peter; Patty, C.Wayne (1987), Foundations of Higher Mathematics, PWS-Kent, ISBN 0-87150-164-3
Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics: An Applied Introduction (3rd izd.), ISBN 978-0-201-54983-6
Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1-114-54101-6

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

[Herstein64-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$ .

[1]

[2]

[3]

[4]

[5]

[6]

[7]