Shih burimin për Parimi i kafazit të pëllumbave

{{Infobox person
| name               = Peter Gustav Lejeune Dirichlet
| image              = Peter Gustav Lejeune Dirichlet.jpg
| birth_date         = 13 Shkurt 1805
| birth_place        = Düren, French Empire
| death_date         = 5 Maj 1859 (mosha 54)
| death_place        = Göttingen, Kingdom of Hanover
| nationality        = Gjerman
| awards             = PhD (Hon):
University of Bonn (1827)
Pour le Mérite (1855)
}}

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.<ref name=":0">{{Cite book|last=Herstein|first=I.N|title=Topics In Algebra|publisher=Waltham: Blaisdell Publishing Company|year=1964|isbn=978-1114541016|pages=90}}</ref>  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]] <ref>{{Cite web|last=Rittaud, Benoît|first=Heeffer, Albrecht|date=2014|title=The pigeonhole principle, two centuries before Dirichlet|url=https://biblio.ugent.be/publication/4115264|url-status=bot: unknown|archive-url=https://web.archive.org/web/20211225205134/https://biblio.ugent.be/publication/4115264|access-date=26/01/2022|website=Academic Bibliograpgy|archive-date=25 dhjetor 2021}}</ref>, zakonisht quhet '''parimi i kutisë së Dirichlet-it''' ose '''parimi i sirtarit të Dirichlet-it''' pas një trajtimi të parimit të vitit 1834 nga [[:en:Peter_Gustav_Lejeune_Dirichlet|Peter Gustav Lejeune Dirichlet]] nën emrin ''Schubfachprinzip'' ("parimi i sirtarit"  ose "parimi i raftit"). <ref>{{Cite web|title=Earliest Known Uses of Some of the Words of Mathematics (P)|url=https://jeff560.tripod.com/p.html|access-date=2022-01-26|website=jeff560.tripod.com}}</ref> 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.<ref>{{Cite book|last=Peter|first=Fletcher|title=Foundations of Higher Mathematics|url=https://archive.org/details/foundationsofhig0000flet_s9r9|last2=Patty|first2=C.Wayne|publisher=PWS-Kent|year=1987|isbn=978-0-87150-164-6|pages=[https://archive.org/details/foundationsofhig0000flet_s9r9/page/27 27]}}</ref>  Për ''n'' dhe ''m'' arbitrar  përgjithësohet në <math>k + 1 = \lfloor(n-1)/m\rfloor+1=</math><math>\lceil n/m\rceil</math>, ku <math>\lfloor ...\rfloor dhe \lceil ...\rceil</math>  tregojnë për funksionet [[:en:Floor_and_ceiling_functions|floor]] dhe [[:en:Floor_and_ceiling_functions|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ë [[Këlni|Cologne]], [[Gjermania|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ë [[Boni|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ë [[:en:University_of_Paris|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 [[Carl Friedrich Gauss|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ë 
[[Skeda:TooManyPigeons.jpg|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ë [[Pierre de Fermat|Fermatit]], se nuk ka zgjidhje jo të parëndësishme në numra të plotë për ''x<sup>5</sup> + y<sup>5</sup> = z<sup>5</sup>''. 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 Bartholdy|Felix Mendelssohn]]. <ref>{{Cite book|last=Rosen|first=Kenneth H.|title=Discrete mathematics and its applications|url=https://archive.org/details/discretemathemat0000rose_8ed|publisher=McGraw-Hill Education|year=2019|isbn=978-1-259-67651-2|pages=[https://archive.org/details/discretemathemat0000rose_8ed/page/n446 421]}}</ref>

== 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''<nowiki/>' 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 [[:en:Graph_(discrete_mathematics)|graf]] me më shumë se një kulm, ka të paktën një palë kulme që ndajnë të njëjtën shkallë.<ref>{{Cite web|last=Pandey|first=Avinash|title=D3 Graph Theory - Interactive Graph Theory Tutorials|url=https://d3gt.com/unit.html?pigeonhole|url-status=live|access-date=26/01/2022|website=D3 GraphTheory}}</ref> Kjo mund të shihet duke e lidhur çdo person me një kulm dhe çdo skaj me një shtrëngim duarsh.

=== Problemi i ditëlindjes ===
[[:en:Birthday_problem|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:

<math>\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</math>

=== 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ë. <ref>{{Cite book|last=Grimaldi|first=Ralph P.|title=Discrete and Combinatorial Mathematics: An Applied Introduction (3rd edition)|url=https://archive.org/details/discretecombinat00grim_1|publisher=Addison-Wesley|year=1994|isbn=978-0-201-54983-6|pages=[https://archive.org/details/discretecombinat00grim_1/page/277 277]}}</ref>

== 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.<ref name=":0"/>

2. Nëse ''n'' objekte shpërndahen në ''m'' kuti(vende), dhe nëse ''n < m'', atëherë një vend nuk merr asnjë objekt.<ref>{{Cite book|last=Brualdi|first=Richard A.|title=Introductory Combinatorics (5th ed.)|publisher=Pentice Hall|year=2010|isbn=978-0-13-602040-0|pages=70}}</ref>

== Forma e fortë ==
Le të jenë q<sub>1</sub>, q<sub>2</sub>, ..., q<sub>n</sub> numra të plotë pozitiv. Nëse  ''q<sub>1</sub> + q<sub>2</sub> + ... + q<sub>n</sub> - n + 1'' objekte shpërndahen në ''n'' kuti, atëherë ose kutia e parë përmban të paktën q<sub>1</sub> objekte, ose kutia e dytë përmban të paktën q<sub>2</sub> objekte, ..., ose kutia e n-të përmban të paktën q<sub>n</sub> objekte.<ref>{{Cite book|last=Brualdi|first=Richard A.|title=Introductory Combinatorics (5th ed.)|publisher=Pentice Hall|year=2010|isbn=978-0-13-602040-0|pages=74 Theorem 3.2.1}}</ref>

Forma e thjeshtë përftohet nga kjo duke marrë q<sub>1</sub> = q<sub>2</sub> = ... = q<sub>n</sub> = 2, e cila jep ''n + 1'' objekte. Marrja e q<sub>1</sub> = q<sub>2</sub> = ... = q<sub>n</sub> = 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 <math>\left \lceil \frac{N}{k} \right \rceil</math> objekte.''

'''Prova:''' Ne do të përdorim një provë me kontradiksion. Supozoni se asnjë nga kutitë nuk përmban më shumë se <math>\left \lceil \frac{N}{k} \right \rceil</math> − 1 objekte. Atëherë, numri i përgjithshëm i objekteve është :

<math>k\Bigl(\left \lceil \frac{N}{k} \right \rceil- 1\Bigr) < k \Bigl(\left ( \frac{N}{k} + 1 \right ) - 1\biggr) = N</math> ,

ku është përdorur inekuaconi <math>\left \lceil \frac{N}{k} \right \rceil < \left ( \frac{N}{k}\right ) + 1</math> . Ky është një kontradiksion, pasi janë 𝑁 objekte në total, ndërkoh që numri i objekteve rezultoi të jetë rigorozisht më i vogël se 𝑁.<ref>{{Cite book|last=Rosen|first=Kenneth H.|title=Discrete mathematics and its applications|url=https://archive.org/details/discretemathemat0000rose_8ed|publisher=McGraw-Hill Education|year=2019|isbn=978-1-259-67651-2|pages=[https://archive.org/details/discretemathemat0000rose_8ed/page/n447 422]}}</ref>

''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ë 𝑎<sub>1</sub>, 𝑎<sub>2</sub>, . . . , 𝑎<sub>𝑛+1</sub> si fuqi e dyshit shumëzim një numër të plotë tek. Një fjalë të tjera, le të jetë 𝑎<sub>𝑗</sub> = 2 <sup>𝑘𝑗</sup><sub>𝑞𝑗</sub> për 𝑗 = 1, 2, . . . , 𝑛 + 1, ku 𝑘<sub>𝑗</sub> është një numër i plotë jonegativ dhe 𝑞<sub>𝑗</sub> është numër tek. Numrat 𝑞<sub>1</sub>, 𝑞<sub>2</sub>, . . . , 𝑎<sub>𝑛+1</sub> 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ë 𝑞<sub>1</sub>, 𝑞<sub>2</sub>, . . . , 𝑞<sub>𝑛+1</sub> 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ë 𝑞<sub>𝑖</sub> = 𝑞<sub>𝑗</sub> . Le të jetë 𝑞 vlera 𝑞<sub>𝑖</sub> dhe 𝑞<sub>𝑗</sub> . Atëherë 𝑎<sub>𝑖</sub> = 2 <sup>𝑘𝑖</sup>𝑞 dhe 𝑎<sub>𝑗</sub> = 2 <sup>𝑘𝑗</sup>𝑞. Rrjedh se nëse 𝑘<sub>𝑖</sub> < 𝑘<sub>𝑗</sub> atëherë 𝑎<sub>𝑖</sub> plotpjeston 𝑎<sub>𝑗</sub> , ndërkohë që nëse 𝑘<sub>𝑖</sub> > 𝑘<sub>𝑗</sub> , rrjedh se 𝑎<sub>𝑗</sub> plotpjeston 𝑎<sub>𝑖</sub> .

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 𝑎<sub>1</sub>, 𝑎<sub>2</sub>, . . . , 𝑎<sub>𝑁</sub> ë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 = 3<sup>2</sup> + 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ë 𝑎<sub>1</sub>, 𝑎<sub>2</sub>, . . . , 𝑎<sub>𝑛 2+1</sub> një varg i 𝑛 <sup>2</sup> + 1 numrave real të ndryshëm. I bashkëshoqërojmë çdo termi 𝑎<sub>𝑘</sub> të vargut një çift të renditur (𝑖<sub>𝑘</sub>, 𝑑<sub>𝑘</sub>), ku 𝑖<sub>𝑘</sub> është gjatësia e nëvargut rritës më të gjatë me fillim në 𝑎<sub>𝑘</sub>, dhe 𝑑<sub>𝑘</sub> është gjatësia e nënvargut më të gjatë zbritës me fillim në 𝑎<sub>𝑘</sub>. Supozojmë se nuk ekzistojnë nënvargje rritës ose zbritës me gjatësi 𝑛 + 1. Atëherë 𝑖<sub>𝑘</sub> dhe 𝑑<sub>𝑘</sub> janë njëkohësisht, numra të plotë pozitiv më të vegjël ose të barabartë me 𝑛, për 𝑘 = 1, 2, . . . , (𝑛<sup>2</sup> + 1). Kështu, nga parimi i shumëzimit, ekzistojnë 𝑛<sup>2</sup> çifte të renditur të mundshëm për (𝑖<sub>𝑘</sub>, 𝑑<sub>𝑘</sub>). Nisur nga parimi i kafazit të pëllumbave, dy prej   𝑛<sup>2</sup> + 1 çfiteve të renditura, janë të barabarta. Në fjalë të tjera, ekzistojnë termat 𝑎<sub>𝑠</sub> dhe 𝑎<sub>𝑡</sub> , të tillë që 𝑠 < 𝑡 të tillë që 𝑖<sub>𝑠</sub> = 𝑖<sub>𝑡</sub> dhe 𝑑<sub>𝑠</sub> = 𝑑<sub>𝑡</sub> . Do të tregojmë që kjo është e pamundur. Duke qënë se termat e vargut janë të ndryshëm, as 𝑎<sub>𝑠</sub> < a<sub>𝑡</sub> dhe as 𝑎<sub>𝑠</sub> > 𝑎<sub>𝑡</sub> . Nëse 𝑎<sub>𝑠</sub> < 𝑎<sub>𝑡</sub> , atëherë duke qënë se 𝑖<sub>𝑠</sub> = 𝑖<sub>𝑡</sub> , mund të ndërtohet një nëvarg rritës me gjatësi 𝑖<sub>𝑡</sub> + 1 me fillim në 𝑎<sub>𝑠</sub> , duke marr 𝑎<sub>𝑠</sub> të tillë që të pasohet nga një nënvarg rritës me gjatësi 𝑖<sub>𝑡</sub> me fillim në 𝑎<sub>𝑡</sub> . Ky është një kontradiksion. Në mënyrë të ngjashme, nëse 𝑎<sub>𝑠</sub> > 𝑎<sub>𝑡</sub> , duke përdorur të njëjtën mënyrë arsyetimi tregohet që 𝑑<sub>𝑠</sub> duhet të jetë më i madh se 𝑑<sub>𝑡</sub> , e cila përbën një kontradiksion. <ref name=":1">{{Cite book|last=Rosen|first=Kenneth H.|title=Discrete mathematics and its applications|year=2003|url=https://archive.org/details/discretemathemat0005rose|publisher=McGraw-Hill Education|isbn=978-1-259-67651-2}}</ref><ref name=":2">{{Cite web|last=Gjermëni|first=Orgeta|title=Parimi i kafazit të pëllumbave|url=https://orgetagjermeni.files.wordpress.com/2018/12/nr13.pdf|url-status=dead|access-date=26/01/2022|archive-date=26 janar 2022|archive-url=https://web.archive.org/web/20220126223142/https://orgetagjermeni.files.wordpress.com/2018/12/nr13.pdf}}</ref>

== Teoria e Ramsey ==
Parimi i kafazit të pëllumbave mund të aplikohet edhe në një pjesë shumë të rëndësishme të [[Kombinatorika|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. <ref name=":1"/><ref name=":2"/>

== Referime ==
{{Reflist}}
.