Principi i Dirileut

Në matematikë, Principi i Dirileut thotë se nëse  elemente ndahen në   grupime, nëse , 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ë  dhe , nëse  objekte shpërndahen në  grupe, atëherë principi i Dirileut pohon se të paktën një grup do të përmbajë të paktën  objekte.Për  dhe  janë numra arbitrar kjo gjeneralizohet në  ku  dhe  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   persona që mund të shtrëngojnë duart me njëri-tjetrin (ku ), 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ë , atëherë gjithëmonë kemi  kafaze të mundëshme. Në anën tjetër, ose kafazi '0'  ose kafazi  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ë  persona të vendosen në më së shumti  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  elemente), me vetëm 4 ekipe  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:



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

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

 Nëse  objekte janë të shpërndara në  vende, dhe nëse , atëherë një vend i pranon të paktën dy objekte.
 (Ekuivalente me formulimin 1)  Nëse  objekte shpërndahen 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.
 Nëse  objekte janë të distributuara në  vende, dhe nëse , atëherë ndonjë vend nuk pranon asnjë objekt.
 (Ekuivalente me formulimin 3)Nëse  objekte janë të shpërndara në   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  pëllumba vendosen rastësisht në  kafaze me probabilitet uniform , pastaj të paktën një kafaz do të përmbajë më shumë se një pëllumb me probabilitet



ku  është faktorieli në rënie . Për  dhe për  (dhe ), ai probabilitet është zero; me fjalë të tjera, nëse kemi vetëm një pëllumb, nuk mund të ketë konflik. Për  (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 (), 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