Dirichletov princip

Fotografija golubova u kutijama. U ovom se primjeru Predložak:Nowrap golubova nalazi u Predložak:Nowrap kutija, pa po Diricletovom principu slijedi da najmanje jedna kutija ima više od jednog goluba.

Dirichletov princip ili princip golubinjaka jednostavan je i djelotvoran kombinatorni princip kojeg je prvi formulirao i koristio njemački matematičar Dirichlet otprilike 1834. godine pod nazivom Schubfachprinzip.

Naime, Dirichletov princip navodi da ako se n golubova smjesti u m golubinjaka, pri čemu je n>m, onda postoji najmanje jedan golubinjak u kojem se nalaze barem dva goluba.

Apstraktna definicija gore navedenog je da, ako je potrebno rasporediti više od n objekata u n nepraznih skupova, onda će barem jedan skup sadržavati više od jednog elementa. Alternativno, ni jedna funkcija iz skupa koji ima više od n elemenata u skup koji ima n elemenata ne može biti injektivna.

Dirichletov princip — slaba forma

Neka je $n$ prirodan broj. Ako $n+1$ predmeta bilo kako rasporedimo u n kutija (pretinaca), tada barem jedna kutija sadrži barem dva predmeta.

Dokažimo tvrdnju kontradikcijom: pretpostavimo da ne postoji kutija koja sadrži više od jednog predmeta. To znači da svaka od $n$ kutija sadrži ili jedan ili nijedan predmet. Označimo s $m$ broj praznih kutija. Vrijedi $m\ge 0$. Tada će broj kutija koje sadrže jedan predmet biti $n-m$. To bi značilo da je ukupan broj predmeta smještenih u $n$ kutija jednak $n-m$, a to je u kontradikciji s pretpostavkom da želimo smjestiti $n+1$ predmet u n kutija, a $n-m\le n<n+1$.

Zato je naša pretpostavka o nepostojanju kutije koja sadrži više od jednog predmeta pogrešna! Valja uočiti da Dirichletov princip daje samo egzistenciju kutije s barem dva predmeta, ne i algoritam njenog pronalaska.

Označimo s $|A|$ broj elemenata skupa $A$. Dirichletov princip može se iskazati i ovako:

Neka su $S$ i $T$ konačni skupovi, takvi da je $|S|>|T|$, a $f:S\to T$ neko preslikavanje. Tada $f$ nije injekcija, tj. postoje $x,x^{\prime }\in S$, $x^{\prime }\ne x$, takvi da je $f(x)=f(x^{\prime })$.

Vrijedi:

Neka su $S,T$ konačni skupovi sa $|S|=|T|=n,af:S\to T$ neko preslikavanje. Tada je $f$ injekcija.

Dirichletov princip — jaka forma

Ako je $m$ predmeta razmješteno u $n$ kutija, onda barem jedna kutija sadrži $\lfloor \frac{m-1}{n}\rfloor +1$ predmet.

Ramseyjeva teorija

Poopćenje Dirichletova principa može se naći u Ramseyjevoj teoriji, matematičkoj teoriji nazvanoj po engleskom matematičaru Franku P. Ramseyju (1903. – 1930.). Srce teorije je Ramseyjev teorem.

Iskaz teorema glasi ovako:

Za svako $r,m\in \mathbb{N}$ i sve prirodne brojeve $r_1,r_2,...,r_m\ge r$ postoji najmanji prirodni broj $N=N(r_1,r_2,...,r_m;r)$, tako velik da ako imamo skup od $n$ elemenata, $n\ge N$ i ako u tom skupu razvrstamo sve $r$-podskupove u $m$ klasa $K_1,K_2,...,K_m$ onda postoji:

ili $r_1$ elemenata čiji su svi $r$-podskupovi u klasi $K_1$,

ili $r_2$ elemenata čiji su svi $r$-podskupovi u klasi $K_2$,

.

.

.

ili $r_m$ elemenata čiji su svi $r$-podskupovi u klasi $K_m$.

Broj $N(r_1,r_2,...,r_m;r)$ zove se (opći) Ramseyjev broj.

Slučaj kada je $r=2$

Za $N(p,q;2):=N(p,q)$ Ramseyjev broj može se definirati kao najmanji broj vrhova nekog potpunog grafa tako da ako je svaka spojnica obojena plavom ili crvenom bojom, onda postoji potpun podgraf s $p$ vrhova čije su sve spojnice plave ili potpun podgraf s $q$ vrhova čije su sve spojnice crvene.