Principi i Dirileut

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ë)

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

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.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 Stampa:Math persona që mund të shtrëngojnë duart me njëri-tjetrin (ku Stampa:Math), 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ë Stampa:Math, atëherë gjithëmonë kemi Stampa:Math kafaze të mundëshme. Në anën tjetër, ose kafazi '0' ose kafazi Stampa:Math 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ë Stampa:Math persona të vendosen në më së shumti Stampa:Math 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ë. 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 Stampa:Math elemente), me vetëm 4 ekipe Stampa:Math 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:

$\lfloor \frac{n-1}{m}\rfloor +1=\lfloor \frac{7-1}{4}\rfloor +1=\lfloor \frac{6}{4}\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 Stampa:Math, bashkësia {[[[:Stampa:Math]] ë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ë Stampa:Math ashtu që Stampa:Math, ku Stampa:Math është një numër i vogël pozitiv dhe Stampa:Math është numër iracional arbitrar. Por nëse e marrim Stampa:Math ashtu që Stampa:Math, në bazë të principit të Dirileut duhet të ekzistojë Stampa:Math} ashtu që Stampa:Math dhe Stampa:Math janë në të njejtën nënndarje te numrave të plotë me madhësinë Stampa:Math (ka vetëm Stampa:Math nënndarje të tilla në mes të numrave të plotë të njëpasnjëshëm).Në veçanti, mund të gjejmë Stampa:Math ashtu që Stampa:Math është në Stampa:Math, dhe Stampa:Math është në Stampa:Math, për ndonjë Stampa:Math numra të plotë dhe Stampa:Math në Stampa:Math}. Pastaj lehtë vërehet se Stampa:Math është në Stampa:Math. Kjo implikon se Stampa:Math, ku Stampa:Math ose Stampa:Math. Kjo tregon se 0 është pika kufitare e {[[[:Stampa:Math]]]}. kjo mund të përdoret që të vërtetojmë rastin për Stampa:Math në Stampa:Math: gjejmë një Stampa:Math ashtu që Stampa:Math; dhe nëse Stampa:Math], vërtetimi është i përfunduar. Përndryshe Stampa:Math], dhe duke caktuar Stampa:Math}, marrim se Stampa:Math.

Formulime alternative

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

1. Nëse Stampa:Math objekte janë të shpërndara në Stampa:Math vende, dhe nëse Stampa:Math, atëherë një vend i pranon të paktën dy objekte.
2. (Ekuivalente me formulimin 1) Nëse Stampa:Math objekte shpërndahen në Stampa:Math 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.
3. Nëse Stampa:Math objekte janë të distributuara në Stampa:Math vende, dhe nëse Stampa:Math, atëherë ndonjë vend nuk pranon asnjë objekt.
4. (Ekuivalente me formulimin 3)Nëse Stampa:Math objekte janë të shpërndara në Stampa:Math vende ashtu që asnjë vend të mos ketë asnjë objekt, dhe pastaj çdo vend pranon saktësishtë një objekt.

Gjeneralizimi i principit të Dirileut

Një gjeneralizim në probabilitet i principit të Dirileut thotë se nëse Stampa:Math pëllumba vendosen rastësisht në Stampa:Math kafaze me probabilitet uniform Stampa:Math, 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 Stampa:Math është faktorieli në rënie Stampa:Math. Për Stampa:Math dhe për Stampa:Math (dhe Stampa:Math), ai probabilitet është zero; me fjalë të tjera, nëse kemi vetëm një pëllumb, nuk mund të ketë konflik. Për Stampa:Math (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 (Stampa:Math), 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.