Parimi i kafazit të pëllumbave
editNë matematikë, parimi i kafazit të pëllumbave është një metodë e thjeshtë, intuitive dhe shpesh e dobishme për të bërë pohime të caktuara rreth një grupi të fundëm.Ky parim përdoret shpesh në matematikë diskrete dhe thotë se nëse n objekte vendosen në m kuti dhe n > m, atëherë të paktën një kuti do të përmbajë më shumë se një objekt.[1]
Emri i parimit lindi nga shembulli i dhënë për kafazin e pëllumbave, ku nëse n=10 pëllumba dhe m=9 kafaze dihet se 10 > 9, prandaj parimi thotë se egziston të paktën një kafaz i cili përmban më shumë se një pëllumb. Për vërtetimin e ketij parimi përdorim teknikën e vërtetimit me kontrapozitiv. Supozojmë se asnjë prej nëntë kafazeve nuk përmban më shumë se një objekt. Atëherë numri i objekteve do të ishte të shumtën 9. Kjo nuk është e mundur sepse bië në kundërshtim me parimin i cili thotë se n > m.
Edhe pse parimi i kafazit të pëllumbave u shfaq për herë të parë në vitin 1624 në një libër që i atribuohet Jean Leurechon, ai ndryshe quhet edhe parimi i kutisë së Dirichletit ose parimi i sirtarit të Dirichletit pasi u trajtua edhe njëherë në vitin 1834 nga Peter Gustav Lejeune Dirichlet sipas emrit Schubfachprinzip (parimi i sirtarit).[2]
Megjithëse aplikimi më i drejtpërdrejtë është për bashkësi të fundme (si kafazet dhe kutitë), ai përdoret gjithashtu me bashkësi të pafundme që nuk mund të vendosen në korrespondencën një-me-një. Për ta bërë këtë kërkon deklaratën formale të parimit të kafazit të pëllumbit, i cili është "nuk ekziston një funksion injektiv, kodomeni i të cilit është më i vogël se domeni i tij". Provat e avancuara matematikore si lema e Siegel-it (Siegel's lemma) bazohen në këtë koncept më të përgjithshëm.
Shembuj
editMegjithë thjeshtësinë e tij, ju mund të bëni deklarata të caktuara me parimin e pëllumbave, për shembull se ka të paktën dy njerëz në Kosovë që kanë saktësisht të njëjtin numër qimesh në kokë. Vërtetim: Të gjithë banorët e Kosovës janë të ndarë në “sirtarë" sipas numrit të qimeve që kanë. Në mënyrë tipike, njerëzit kanë rreth 100,000 deri në 200,000, por sigurisht më pak se 1 milion qime, kështu që ka një maksimum prej një milion sirtarë (nga 0 në 999,999). Por duke qenë se në Kosovë ka rreth 1.9 milionë banorë, ka më shumë banorë sesa sirtarë, kështu që dy ose më shumë njerëz përfundojnë në të paktën një sirtar. Sipas përcaktimit të sirtarëve, ata kanë të njëjtin numër qimesh në kokë.
Një shembull tjetër është deklarata se në një grup prej 13 personash të paktën dy kanë ditëlindjen në të njëjtin muaj (sepse janë vetëm 12 muaj).[1]
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ëllumbit, për të pasur të paktën një pale çorape të së njëjtës ngjyrë (m = 2 kafaze, 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.
Referenca
edit- ^ a b H., Rosen, Kenneth (2013). Discrete mathematics and its applications : seventh edition. McGraw-Hill. ISBN 978-0-07-131501-2. OCLC 813136404.
{{cite book}}: CS1 maint: multiple names: authors list (link) - ^ Rebman, Kenneth R. (1979-01). "The Pigeonhole Principle (What It Is, How It Works, and How It Applies to Map Coloring)". The Two-Year College Mathematics Journal. 10 (1): 3. doi:10.2307/3026807.
{{cite journal}}: Check date values in:|date=(help)