Dirichletov princip

Fotografija golubova u kutijama. U ovom se primjeru n = 10 golubova nalazi u m = 9 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\geq 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\leq 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\rightarrow T$ neko preslikavanje. Tada $f$ nije injekcija, tj. postoje $x,x'\in S$, $x'\neq x$, takvi da je $f(x)=f(x')$.

Vrijedi:

Neka su $S,T$ konačni skupovi sa $|S|=|T|=n,af:S\rightarrow 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 $\left\lfloor {\frac {m-1}{n}}\right\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}\geq r$ postoji najmanji prirodni broj $N=N(r_{1},r_{2},...,r_{m};r)$, tako velik da ako imamo skup od $n$ elemenata, $n\geq 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.