Principi i Dirileut

Nuk ka versione të shqyrtuara të kësaj faqe, ndaj mund të mos jetë kontrolluar përputhja e saj me standardet.

Në matematikë, Principi i Dirileut thotë se nëse $n$ elemente ndahen në $m$ grupime, nëse $n>m$ , atëherë të paktën një grupim duhet gjithsesi të përmbajë më shumë se një element.^[1] Për shembull, nëse kemi tri dorëza (dhe asnjëra nuk mund të përdoret për dy duart njëlloj), atëherë duhet të kemi gjithsesi të paktën dy doreza të dorës së djathtë, ose të paktën dy doreza të dorës së majtë, sepse kemi tri objekte, por vetëm dy grupime të dorezave në të cilat mund të vendosen. Kjo deklaratë që është e kuptueshme paraqet një lloj argumenti të kombinatorikës, dhe mund të përdoret për demonstrimin e rezultateve të mundshme të papritura. Për shembull, në qoftë se numri i banorëve të një qyteti është më i madh se numri maksimal i qimeve të flokut që një person mund ti ketë, principi i Dirileut thotë se ekzistojnë të paktën dy persona që jetojnë në atë lokacion me të njejtin numër të qimeve të flokut.

Pëllumbat në kafaze. Kemi 10 pëllumba dhe 9 kafaze. Meqenëse 10>9 nga principi i Dirileut kuptojmë se të paktën një kafaz ka më shumë se një pëllumb.(Kafazi lartë në të djathtë)

Ky princip ka gjeneralizime të shumta që mund të paraqiten në mënyra të ndryshme. Në një mënyrë më të numërueshme për numrat naturorë $k$ dhe $m$ , nëse $n=km+1$ objekte shpërndahen në $m$ grupe, atëherë principi i Dirileut pohon se të paktën një grup do të përmbajë të paktën $k+1$ objekte.^[2]Për $n$ dhe $m$ janë numra arbitrar kjo gjeneralizohet në $k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil ,$ ku $\lfloor \cdots \rfloor$ dhe $\lceil \cdots \rceil$ tregojnë pjesën e poshtme të plotë dhe pjesën e lartë të plotë, respektivisht.

Edhe pse aplikimi më direkt i këtij principi është në bashkësitë e fundme, ai po ashtu përdoret në bashkësitë e pafundme që nuk mund të vendosen në pasqyrim një-një. Kjo kërkon paraqitjen formale të pricipit të Dirileut, e cila thotë " nuk ekziston një funksion injektiv kodomena e të cilit është më e vogël se domena".

Shembull

Shtrëngimi i duarve

Nëse kemi $n$ persona që mund të shtrëngojnë duart me njëri-tjetrin (ku $n > 1$ ), principi i Dirileut tregon se gjithmonë ekziston dy persona të cilët do të shtrëngojnë duart me një numër të njejtë personash. Në këtë shembull të principit, "kafazi" në të cilin personat caktohen është numri i duarve të shtrënguara nga ai person. Meqenëse çdo person shtrëngon duart me një numer personash nga 0 deri në $n - 1$ , atëherë gjithëmonë kemi $n$ kafaze të mundëshme. Në anën tjetër, ose kafazi '0' ose kafazi $' n - 1'$ ose të dy duhet të jenë të zbrazëta, përndryshe është e pamundëshme që një person të shtrëngojë duart me të gjithë personat e tjerë përderisa një person nuk shtrëngon duart me askënd. Kjo lë $n$ persona të vendosen në më së shumti $n - 1$ kafaze të zbrazëta, në mënyrë që principi të vlejë. Ky shembull është ekuivalent me rregullën se në çdo graf me më shumë se një nyje, ka të paktën një çift nyjesh që kanë të njejtën shkallë.^[3] Kjo mund të vërehet nëse çdo person e zëvendësojmë me një nyje dhe çdo skaj me një shtrëngim duarsh

Zgjedhja e qorapeve

Supozojmë se në një dollap kemi qorape të zeza dhe të bardha, të cilat mund të mbathen në cilëndo këmbë, si dhe se po nxjerrim nga dollapi një numër të caktuar qorapesh pa shikuar. Sa është numri minimal i qorapeve të nxjerrura në mënyrë që të kemi të paktën palë qorape të ngjyrës së njejtë? Duke përdorur principin e Dirileut që të kemi një palë qorape të ngjyrës së njejtë duhet të kemi të nxjerrim 3 qorape nga dollapi. Kemi dy raste ose kemi tërhequr tri qorape të ngjyrës së njejtë, ose kemi dy qorape (një palë) të njejtës ngjyrë dhe një të ngjyrës tjetër.

Turnamenti me ekipe

Supozojmë se kemi 7 persona që duan të luajnë në një turnament me ekipe $(n = 7$ elemente), me vetëm 4 ekipe $(m = 4$ kafaze) në të cilët mund të ndahen. Principi i Dirileut na tregon se ata nuk mund të gjithë të luajnë për ekipe të ndyshme;duhet që së paku njëri ekip të ketë së paku 2 prej 7 personave:

\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

Përdorimi dhe aplikimi

Parimi mund të përdoret për të vërtetuar se çdo algoritëm i kompresimit pa humbje, me kusht që t'i bëjë disa hyrje më të vogla (siç sugjeron emri i kompresimit), do t'i bëjë edhe disa hyrje të tjera më të mëdha. Përndryshe, grupi i të gjitha sekuencave hyrëse deri në një gjatësi të caktuar L mund të krahasohet me grupin (shumë) më të vogël të të gjitha sekuencave me gjatësi më të vogël se L pa përplasje (sepse kompresimi është pa humbje), një mundësi që parimi i Dirileut e përjashton.

Një problem i dukshëm në analizën matematikore është, të tregohet se për një numër të pandryshueshëm irracional $a$ , bashkësia {[ $na]: n$ është numër i plotë} e pjesëve të pjesshme është i dendur në [0, 1]. Vërehet se nuk është e lehtë që të gjenden në mënyrë eksplicite numrat e plotë $n, m$ ashtu që $| na - m | < e$ , ku $e > 0$ është një numër i vogël pozitiv dhe $a$ është numër iracional arbitrar. Por nëse e marrim $M$ ashtu që $1/ M < e$ , në bazë të principit të Dirileut duhet të ekzistojë $n 1, n 2 \in {1, 2, ..., M + 1$ } ashtu që $n 1 a$ dhe $n 2 a$ janë në të njejtën nënndarje te numrave të plotë me madhësinë $1/ M$ (ka vetëm $M$ nënndarje të tilla në mes të numrave të plotë të njëpasnjëshëm).Në veçanti, mund të gjejmë $n 1, n 2$ ashtu që $n 1 a$ është në $(p + k / M, p + (k + 1)/ M)$ , dhe $n 2 a$ është në $(q + k / M, q + (k + 1)/ M)$ , për ndonjë $p, q$ numra të plotë dhe $k$ në ${0, 1, ..., M - 1$ }. Pastaj lehtë vërehet se $(n 2 - n 1) a$ është në $(q - p - 1/ M, q - p + 1/ M)$ . Kjo implikon se $[na] < 1/ M < e$ , ku $n = n 2 - n 1$ ose $n = n 1 - n 2$ . Kjo tregon se 0 është pika kufitare e {[ $na$ ]}. kjo mund të përdoret që të vërtetojmë rastin për $p$ në $(0, 1]$ : gjejmë një $n$ ashtu që $[na] < 1/ M < e$ ; dhe nëse $p \in (0, 1/ M$ ], vërtetimi është i përfunduar. Përndryshe $p \in (j / M, (j + 1)/ M$ ], dhe duke caktuar $k = sup{r \in N : r [na] < j / M$ }, marrim se $|[(k + 1) na] - p | < 1/ M < e$ .

Formulime alternative

Këto janë formulime të ndryshme të principit të Dirileut

Nëse $n$ objekte janë të shpërndara në $m$ vende, dhe nëse $n > m$ , atëherë një vend i pranon të paktën dy objekte.^[1]
(Ekuivalente me formulimin 1) Nëse $n$ objekte shpërndahen në $n$ vende në atë mënyrë që asnjë vend të mos pranojë mës humë se një objekt, pastaj çdo vend pranon saktësisht një objekt.^[1]
Nëse $n$ objekte janë të distributuara në $m$ vende, dhe nëse $n < m$ , atëherë ndonjë vend nuk pranon asnjë objekt.
(Ekuivalente me formulimin 3)Nëse $n$ objekte janë të shpërndara në $n$ vende ashtu që asnjë vend të mos ketë asnjë objekt, dhe pastaj çdo vend pranon saktësishtë një objekt.^[4]

Gjeneralizimi i principit të Dirileut

Një gjeneralizim në probabilitet i principit të Dirileut thotë se nëse $n$ pëllumba vendosen rastësisht në $m$ kafaze me probabilitet uniform $1/ m$ , pastaj të paktën një kafaz do të përmbajë më shumë se një pëllumb me probabilitet

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

ku $(m) n$ është faktorieli në rënie $m (m - 1)(m - 2)...(m - n + 1)$ . Për $n = 0$ dhe për $n = 1$ (dhe $m > 0$ ), ai probabilitet është zero; me fjalë të tjera, nëse kemi vetëm një pëllumb, nuk mund të ketë konflik. Për $n > m$ (më shumë pëllumba sesa kafaze) është një, në këtë rast përputhet me principin e rëndomtë të Dirileut. Por edhe nëse numri i pëllumbave nuk e kalon numrin e kafazeve ( $n \leq m$ ), për shkak të natyrës të vendosjes së pëllumbave në kafaze shpesh ekziston mundësia që të ndodhin përplasjet. Për shembull, nëse 2 pëllumba vendosen rastësisht në 4 kafaze, ka 25% shanca që të paktën një kafaz do të ketë më shumë se një pëllumb, për 5 pëllumba dhe 10 kafaze, probabiliteti është 69.79% , për 10 pëllumba dhe 20 kafaze është rreth 93.45%. Nëse numri i kafazeve është i pandryshueshëm, gjithmonë ka probabilitet me të madh i një qifti kur e rrisim numrin e pëllumbave.Ky problem është më i zgjeruar në paradoksin e ditëlindjes.

References

^ ^a ^b ^c Herstein, I.N (1964). Topics In Algebra. Waltham: Blaisdell Publishing Company. fq. 90. ISBN 978-1114541016. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Peter, Fletcher; Patty, C.Wayne (1987). Foundations of Higher Mathematics. PWS-Kent. fq. 27. ISBN 978-0-87150-164-6. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Pandey, Avinash. "D3 Graph Theory - Interactive Graph Theory Tutorials". D3 GraphTheory. Marrë më 26 janar 2022. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)Mirëmbajtja CS1: Gjendja e adresës (lidhja)
^ Brualdi, Richard A. (2010). Introductory Combinatorics (5th ed.). Pentice Hall. fq. 70. ISBN 978-0-13-602040-0. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[:0-1] Herstein, I.N (1964). Topics In Algebra. Waltham: Blaisdell Publishing Company. fq. 90. ISBN 978-1114541016. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[2] Peter, Fletcher; Patty, C.Wayne (1987). Foundations of Higher Mathematics. PWS-Kent. fq. 27. ISBN 978-0-87150-164-6. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[3] Pandey, Avinash. "D3 Graph Theory - Interactive Graph Theory Tutorials". D3 GraphTheory. Marrë më 26 janar 2022. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)Mirëmbajtja CS1: Gjendja e adresës (lidhja)

[4] Brualdi, Richard A. (2010). Introductory Combinatorics (5th ed.). Pentice Hall. fq. 70. ISBN 978-0-13-602040-0. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1]

[2]

[3]

[4]