Parimi i kafazit të pëllumbave

Peter Gustav Lejeune Dirichlet
Lindi	13 Shkurt 1805 Düren, French Empire
Vdiq	5 Maj 1859 (mosha 54) Göttingen, Kingdom of Hanover
Kombësia	Gjerman
Çmimet	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. 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ë $k+1=\lfloor (n-1)/m\rfloor +1=$$\lceil n/m\rceil$, ku $\lfloor ...\rfloor dhe\lceil ...\rceil$ 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ë

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 x⁵ + y⁵ = z⁵. 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:

$\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$

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ë q₁, q₂, ..., q_n numra të plotë pozitiv. Nëse q₁ + q₂ + ... + q_n - n + 1 objekte shpërndahen në n kuti, atëherë ose kutia e parë përmban të paktën q₁ objekte, ose kutia e dytë përmban të paktën q₂ objekte, ..., ose kutia e n-të përmban të paktën q_n objekte.

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

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

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

ku është përdorur inekuaconi $\left\lceil {\frac {N}{k}}\right\rceil <\left({\frac {N}{k}}\right)+1$ . 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 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 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 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 𝑎₁, 𝑎₂, . . . , 𝑎_𝑁 ë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² + 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ë 𝑎₁, 𝑎₂, . . . , 𝑎_{𝑛 2+1} një varg i 𝑛 ² + 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, . . . , (𝑛² + 1). Kështu, nga parimi i shumëzimit, ekzistojnë 𝑛² çifte të renditur të mundshëm për (𝑖_𝑘, 𝑑_𝑘). Nisur nga parimi i kafazit të pëllumbave, dy prej 𝑛² + 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

.