Parimi i kafazit të pëllumbave

Në matematikë, parimi i kafazit të pëllumbave thotë se nëse n objekte vendosen në m kuti, ku n>m, atëherë të paktën një kuti duhet të përmbajë më shumë se një objekt.  Për shembull, nëse dikush ka tre doreza (dhe asnjëra nuk është e dyfishtë / e kthyeshme), atëherë duhet të ketë të paktën dy doreza të dorës së djathtë, ose të paktën dy doreza të dorës së majtë, sepse ka tre objekte, por vetëm dy kategori të duarve. Kjo deklaratë në dukje e qartë, një lloj argumenti numërimi, mund të përdoret për të demonstruar rezultate ndoshta të papritura. Për shembull, duke pasur parasysh se popullsia e Londrës është më e madhe se numri maksimal i flokëve që mund të jenë të pranishëm në kokën e një njeriu, atëherë parimi i kafazit së pëllumbit kërkon të tregojë që duhet të ketë të paktën dy njerëz në Londër që kanë të njëjtin numër flokësh në kokën e tyre. 

Megjithëse parimi i kafazit të pëllumbit shfaqet qysh në vitin 1624 në një libër që i atribuohet Jean Leurechon , zakonisht quhet parimi i kutisë së Dirichlet-it ose parimi i sirtarit të Dirichlet-it pas një trajtimi të parimit të vitit 1834 nga Peter Gustav Lejeune Dirichlet nën emrin Schubfachprinzip ("parimi i sirtarit"  ose "parimi i raftit").  Parimi ka disa përgjithësime dhe mund të shprehet në mënyra të ndryshme. Në një version: për numrat natyralë k dhe m, nëse  n = km + 1 objekte shpërndahen mes m grupeve, atëherë parimi i kafazit të pëllumbave pohon se të paktën një nga grupet do të përmbajë të paktën k + 1 objekte.  Për n dhe m arbitrar  përgjithësohet në , ku   tregojnë për funksionet floor dhe ceiling (pjesa e poshtme dhe e sipërme e plotë).

 Biografia e G. LEJEUNE DIRICHLET 
G. Lejeune Dirichlet lindi në një familje belge që jetonte pranë Cologne, Gjermani. Babai i tij ishte drejtor poste. Ai u bë i pasionuar pas matematikës që në moshë të re. Ai shpenzonte të gjitha paratë e tij rezervë për librat e matematikës në kohën kur ai hyri në shkollën e mesme në Bonn në moshën 12 vjeç. Në moshën 14 vjeç ai hyri në Kolegjin Jezuit në Cologne, dhe në moshën 16 vjeç ai filloi studimet e tij në Universitetin e Parisit. Në 1825 ai u kthye në Gjermani dhe u emërua në një pozicion në Universitetin e Breslau-t. Në 1828 u transferua në Universitetin e Berlinit. Në 1855 ai u zgjodh për të pasuar Gauss-in në Universitetin e Gottingen. Dirichlet thuhet se është personi i parë që kreu master për Disquisitiones Arithmeticae(nga gjuha latine, Hetimet aritmetike) të Gaussit, i cili u shfaq 20 vjet më parë. Thuhet se ai kishte mbajtur një kopje pranë tij edhe kur udhëtonte. 

Dirichlet bëri shumë zbulime të rëndësishme në teorinë e numrave, duke përfshirë teoremën se ka pafundësisht shumë numra të thjeshtë në 
parapamje|Pëllumba në kafaz. Këtu ka n = 10 pëllumba në m = 9 vrima të kafazit. Meqenëse 10 është më e madhe se 9, parimi i kafazit të pëllumbit thotë se të paktën një kafaz ka më shumë se një pëllumb. (Kafazi i sipërm majtas ka 2 pëllumba.)
progresionet aritmetike an + b kur a dhe b janë relativisht të thjeshtë. Ai vërtetoi rastin n = 5 të teoremës së fundit të Fermatit, se nuk ka zgjidhje jo të parëndësishme në numra të plotë për x5 + y5 = z5. Dirichlet dha gjithashtu shumë kontribute në analizë. Dirichlet konsiderohej të ishte një mësues i shkëlqyer që mund të shpjegonte idetë me qartësi të madhe. Ai ishte i martuar me Rebecka Mendelssohn, një nga motrat e kompozitorit Felix Mendelssohn. 

 Shembuj 

 Përzgjedhja e çorapeve 
Supozoni se një sirtar përmban një përzierje çorape të zeza dhe çorape blu, secila prej të cilave mund të vishen në të dyja këmbët, dhe se po tërhiqni një numër çorapësh nga sirtari pa i parë. Cili është numri minimal i çorapeve të tërhequra që kërkohet për të garantuar një palë me të njëjtën ngjyrë? Duke përdorur parimin e kafazit të pëllumbave, për të pasur të paktën një palë të së njëjtës ngjyrë (m = 2 vrima, një për ngjyrë) duke përdorur një kafaz pëllumbi për ngjyrë, duhet të tërhiqni vetëm tre çorape nga sirtari (n = 3 artikuj). Ose keni tre të një ngjyre, ose keni dy të njërës ngjyrë dhe një nga tjetra.

 Shtrëngimi i duarve 
Nëse ka n njerëz që mund të shtrëngojnë duart me njëri-tjetrin (ku n > 1), parimi i kafazit të pëllumbave tregon se ka gjithmonë një palë njerëzish që do të shtrëngojnë duart me të njëjtin numër njerëzish. Në këtë zbatim të parimit, 'kafazi(vrima)' së cilës i caktohet një person është numri i duarve të tundura nga ai person. Meqenëse çdo person shtrëngon duart me një numër njerëzish nga 0 në n − 1, ka n vrima të mundshme. Nga ana tjetër, ose vrima '0' ose vrima n − 1' ose të dyja duhet të jenë bosh, sepse është e pamundur (nëse n > 1) që një person të shtrëngojë dorën me të gjithë të tjerët ndërsa dikush shtrëngon duart me asnjë. Kjo lë n njerëz të vendosen në maksimum n − 1 vrima jo bosh, në mënyrë që parimi të zbatohet.

Ky shembull i shtrëngimit të dorës është i barabartë me pohimin se në çdo graf me më shumë se një kulm, ka të paktën një palë kulme që ndajnë të njëjtën shkallë. Kjo mund të shihet duke e lidhur çdo person me një kulm dhe çdo skaj me një shtrëngim duarsh.

 Problemi i ditëlindjes 
Problemi i ditëlindjes pyet, për një grup prej n personash të zgjedhur rastësisht, sa është probabiliteti që disa prej tyre të kenë të njëjtën ditëlindje? Vetë problemi ka të bëjë kryesisht me probabilitetet kundërintuitive; megjithatë, ne mund të themi gjithashtu nga parimi i kafazit të pëllumbave se, nëse ka 367 njerëz në dhomë, ka të paktën një palë njerëzish që ndajnë të njëjtën ditëlindje me probabilitet 100%, pasi ka vetëm 366 ditëlindje të mundshme për të zgjedhur ( duke përfshirë 29 shkurtin, nëse është i pranishëm).

 Turnet Ekipore 
Imagjinoni shtatë persona që duan të luajnë në një turne skuadrash (n = 7 artikuj), me një kufizim prej vetëm katër skuadrash (m = 4 vrima) për të zgjedhur. Parimi i pëllumbave na thotë se nuk mund të luajnë të gjithë për ekipe të ndryshme; duhet të ketë të paktën një ekip me të paktën dy prej shtatë lojtarëve:

 Shuma e nëngrupit 
Çdo nëngrup i madhësisë gjashtë nga grupi S = {1,2,3,...,9} duhet të përmbajë dy elementë, shuma e të cilëve është 10. Vrimat(Kafazet) e pëllumbave do të etiketohen nga dy nëngrupet e elementeve {1,9},    {2 ,8}, {3,7}, {4,6} dhe teke {5}, pesë vrima(kafaze) pëllumbash gjithsej. Kur gjashtë "pëllumbat" (elementet e nëngrupit të madhësisë gjashtë) vendosen në këto vrima pëllumbash, çdo pëllumb që shkon në vrimën e pëllumbit që e ka në etiketën e tij, të paktën një nga vrimat e pëllumbave të etiketuar me një nëngrup me dy elementë do të ketë dy pëllumbat në të. 

 Formulime alternative 
Më poshtë janë formulimet alternative të parimit të kafazit pëllumbave.

1. Nëse n objekte shpërndahen në m kuti(vende), dhe nëse n > m, atëherë një vend merr të paktën dy objekte.

2. Nëse n objekte shpërndahen në m kuti(vende), dhe nëse n < m, atëherë një vend nuk merr asnjë objekt.

 Forma e fortë 
Le të jenë q1, q2, ..., qn numra të plotë pozitiv. Nëse  q1 + q2 + ... + qn - n + 1 objekte shpërndahen në n kuti, atëherë ose kutia e parë përmban të paktën q1 objekte, ose kutia e dytë përmban të paktën q2 objekte, ..., ose kutia e n-të përmban të paktën qn objekte.

Forma e thjeshtë përftohet nga kjo duke marrë q1 = q2 = ... = qn = 2, e cila jep n + 1 objekte. Marrja e q1 = q2 = ... = qn = r jep versionin më sasior të parimit, përkatësisht:

Le të jenë n dhe r numra të plotë pozitivë. Nëse n(r - 1) + 1 objekte shpërndahen në n kuti, atëherë të paktën njëra prej kutive përmban r ose më shumë objekte.

 Parimi i përgjithësuar 
Parimi i kafazit të pëllumbave thotë se duhet të ketë të paktën dy objekte në të njëjtën kuti kur ka më shumë objekte se kuti. Megjithatë, më shumë mund të thuhet kur numri i objekteve tejkalon shumëfishin e numrit të kutive. Për shembull, midis çdo grupi prej 21 shifrash dhjetore duhet të ketë 3 që janë të njëjta. Kjo rrjedh sepse kur 21 objekte shpërndahen në 10 kuti, një kuti duhet të ketë më shumë se 2 objekte.

Parimi i përgjithësuar i kafazit të pëllumbave thotë:  Nësë N objekte vendosen në k kuti, atëherë ka të paktën një kuti që përmban të paktën  objekte.Prova: Ne do të përdorim një provë me kontradiksion. Supozoni se asnjë nga kutitë nuk përmban më shumë se  − 1 objekte. Atëherë, numri i përgjithshëm i objekteve është :

 ,

ku është përdorur inekuaconi  . Ky është një kontradiksion, pasi janë 𝑁 objekte në total, ndërkoh që numri i objekteve rezultoi të jetë rigorozisht më i vogël se 𝑁.Shembull: Ndërmjet 100 njerëzve, janë të paktën ⌈100/12⌉ = 9 të cilët kanë lindur në të njëjtin muaj.

 Disa aplikime elegante të Parimit të Kafazit të Pëllumbave 
Në shumë aplikime interesante të parimit të pëllumbave, objektet që do të vendosen në kuti duhet të zgjidhen në mënyrë të zgjuar. Disa aplikime të tilla do të përshkruhen këtu;Shembull: Tregoni që përgjatë 𝑛 + 1 numrave të plotë pozitiv të cilët nuk e tejkalojnë 2𝑛, ekziston një numër i plotë i cili plotpjeston njërin prej numrave të plotë.Zgjidhje: Shkruajmë secilin prej 𝑛 + 1 numrave të plotë 𝑎1, 𝑎2, . . . , 𝑎𝑛+1 si fuqi e dyshit shumëzim një numër të plotë tek. Një fjalë të tjera, le të jetë 𝑎𝑗 = 2 𝑘𝑗𝑞𝑗 për 𝑗 = 1, 2, . . . , 𝑛 + 1, ku 𝑘𝑗 është një numër i plotë jonegativ dhe 𝑞𝑗 është numër tek. Numrat 𝑞1, 𝑞2, . . . , 𝑎𝑛+1 janë numra të plotë pozitiv më të vegjël se 2𝑛. Duke qënë se janë vetëm 𝑛 numra të plotë pozitiv tek më të vegjël se 2𝑛, nga parimi i kafazit të pëllumbave, rrjedh se dy prej numrave të plotë 𝑞1, 𝑞2, . . . , 𝑞𝑛+1 duhet të jenë të barabartë. Për këtë arsye, ekzistojnë numrat e plotë 𝑖 dhe 𝑗 të ndryshëm nga njëri-tjetri të tillë që 𝑞𝑖 = 𝑞𝑗 . Le të jetë 𝑞 vlera 𝑞𝑖 dhe 𝑞𝑗 . Atëherë 𝑎𝑖 = 2 𝑘𝑖𝑞 dhe 𝑎𝑗 = 2 𝑘𝑗𝑞. Rrjedh se nëse 𝑘𝑖 < 𝑘𝑗 atëherë 𝑎𝑖 plotpjeston 𝑎𝑗 , ndërkohë që nëse 𝑘𝑖 > 𝑘𝑗 , rrjedh se 𝑎𝑗 plotpjeston 𝑎𝑖 .

Një aplikim interesant i parimit të kafazit të pëllumbave tregon ekzistencën e një nënvargu rritës ose zbritës më një gjatësi të caktuar, në një varg numrash të plotë të ndryshëm. Përpara se të shikohet ky aplikim, shikojmë disa përkufizime. Supozojmë se 𝑎1, 𝑎2, . . . , 𝑎𝑁 është një varg numrash real. Një nënvarg i këtij vargu, është një varg i cili përftohet nga vargu fillestar duke përfshirë disa prej termave të vargut fillestar në renditjen që ata kanë, dhe disa të tjera nuk përfshihen. Një varg quhet rigorozisht rritës nëse çdo term është më i madh se termi paraardhës tij, dhe quhet rigorozisht zbritës nëse çdo term është më i vogël se termi paraardhës i tij.

Teoremë: Çdo varg i 𝑛 2 + 1 numrave real të ndryshëm përmban një nënvarg me gjatësi 𝑛 + 1 i cili është rigorozisht rritës ose rigorozisht zbritës.

Përpara se të japim vërtetimin e teoremës, japim një shembull. Shembull: Vargu 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 përmban 10 terma. Vini re që 10 = 32 + 1. Ekzistojnë katër nëvargje rigorozisht rritës me gjatësi katër, të cilët janë 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; dhe 1, 4, 5, 7. Ekziston gjithashtu një nënvarg rigorozisht zbritës me gjatësi katër, i cili është 11, 9, 6, 5.

Në vijim japim vërtetimin e teoremës. Vërtetim: Le të jenë 𝑎1, 𝑎2, . . . , 𝑎𝑛 2+1 një varg i 𝑛 2 + 1 numrave real të ndryshëm. I bashkëshoqërojmë çdo termi 𝑎𝑘 të vargut një çift të renditur (𝑖𝑘, 𝑑𝑘), ku 𝑖𝑘 është gjatësia e nëvargut rritës më të gjatë me fillim në 𝑎𝑘, dhe 𝑑𝑘 është gjatësia e nënvargut më të gjatë zbritës me fillim në 𝑎𝑘. Supozojmë se nuk ekzistojnë nënvargje rritës ose zbritës me gjatësi 𝑛 + 1. Atëherë 𝑖𝑘 dhe 𝑑𝑘 janë njëkohësisht, numra të plotë pozitiv më të vegjël ose të barabartë me 𝑛, për 𝑘 = 1, 2, . . . , (𝑛2 + 1). Kështu, nga parimi i shumëzimit, ekzistojnë 𝑛2 çifte të renditur të mundshëm për (𝑖𝑘, 𝑑𝑘). Nisur nga parimi i kafazit të pëllumbave, dy prej   𝑛2 + 1 çfiteve të renditura, janë të barabarta. Në fjalë të tjera, ekzistojnë termat 𝑎𝑠 dhe 𝑎𝑡 , të tillë që 𝑠 < 𝑡 të tillë që 𝑖𝑠 = 𝑖𝑡 dhe 𝑑𝑠 = 𝑑𝑡 . Do të tregojmë që kjo është e pamundur. Duke qënë se termat e vargut janë të ndryshëm, as 𝑎𝑠 < a𝑡 dhe as 𝑎𝑠 > 𝑎𝑡 . Nëse 𝑎𝑠 < 𝑎𝑡 , atëherë duke qënë se 𝑖𝑠 = 𝑖𝑡 , mund të ndërtohet një nëvarg rritës me gjatësi 𝑖𝑡 + 1 me fillim në 𝑎𝑠 , duke marr 𝑎𝑠 të tillë që të pasohet nga një nënvarg rritës me gjatësi 𝑖𝑡 me fillim në 𝑎𝑡 . Ky është një kontradiksion. Në mënyrë të ngjashme, nëse 𝑎𝑠 > 𝑎𝑡 , duke përdorur të njëjtën mënyrë arsyetimi tregohet që 𝑑𝑠 duhet të jetë më i madh se 𝑑𝑡 , e cila përbën një kontradiksion. 

 Teoria e Ramsey 
Parimi i kafazit të pëllumbave mund të aplikohet edhe në një pjesë shumë të rëndësishme të kombinatorikës e cila njihet si Teoria e Ramsey, për nder të matematikantit Anglez Frank Plumpton Ramsey. Në përgjithësi, teoria Ramsey ka të bëj me shpërndrajet e nënbashkësive të elementëve të një bashkësie.Shembull: Supozojmë që në një grup prej gjashtë njerëzish, çdo çift prej tyre konsiston në dy miq ose në dy armiq. Tregoni që ka ose tre miq ose tre armiq në grup.Zgjidhje:'' Le të jetë 𝐴 njëri prej gjashtë njerëzve. Prej pesë njërëzve të tjerë në grup ekzistojnë tre njërëz ose më shumë të cilët janë miq të 𝐴, ose tre apo më shumë armiq të 𝐴. Kjo rrjedh nga përgjithësimi i parimit të kafazit të pëllumbave, sepse kur pesë objekte ndahen në dy bashkësi, njëra prej bashkësive ka të paktën ⌈5/2⌉ = 3 elementë. Në rastin e përgjithshëm, supozojmë se 𝐵, 𝐶 dhe 𝐷 janë miq të 𝐴. Nëse dy prej këtye tre individëve janë miq, atëherë këta dy dhe 𝐴 formojnë grupin prej tre miqsh. Përndryshme, 𝐵, 𝐶, dhe 𝐷 formojnë një bashkësi të tre armiqve dy e nga dy. Vërtetimi në ratsin tjetër kur, ekzistojnë tre apo më shumë armiq të 𝐴 bëhet në mënyrë të ngjashme.Numrat Ramsey''' 𝑅(𝑚, 𝑛) ku 𝑚 dhe 𝑛 janë numra të plotë pozitiv më të mëdhenj ose të barabartë me 2, tregojnë numrin më të vogël të njerëzve në një festë të tillë që ka ose 𝑚 armiq dy e nga dy ose 𝑛 armiq dy e nga dy, duke supozuar që çdo çift në festë është ose miq ose armiq. Shembulli i mësipërm tregon që 𝑅(3, 3) ≤ 6. Dalim në përfundimin që 𝑅(3, 3) = 6 sepse në një grup prej pesë njërëzish, ku çdo dy njerëz janë ose miq ose armiq, atje nuk mund të ketë tre miq dy e nga dy ose tre armiq dy e nga dy.

Me anë të simetrisë mund të tregohet që 𝑅(𝑚, 𝑛) = 𝑅(𝑛, 𝑚) . Gjithashtu mund të tregohet që 𝑅(2, 𝑛) = 𝑛 për çdo numër të plotë pozitiv 𝑛 ≥ 2. Dihen saktësisht vlerat e vetëm nëntë numrave Ramsey 𝑅(𝑚, 𝑛) ku  3 ≤ 𝑚 ≤ 𝑛, duke përfshirë 𝑅(4, 4) = 18. Vetëm kufijtë njihen për shumicën e numrave të tjerë Ramsey, duke përfshirë këtu 𝑅(5, 5), për të cilën dihet që 43 ≤ 𝑅(5, 5) ≤ 49. 

 Referime 

.