Dirichletov princip

Neka je ${\displaystyle n}$ prirodan broj. Ako ${\displaystyle 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 kojasadrži više od jednog predmeta. To znači da svaka od ${\displaystyle n}$ kutija sadrži ili jedan ili nijedan predmet. Označimo s ${\displaystyle m}$ broj praznih kutija. Vrijedi ${\displaystyle m\geq 0}$ . Tada će broj kutija koje sadrže jedan predmet biti ${\displaystyle n-m}$ . To bi značilo da je ukupanbroj predmeta smještenih u ${\displaystyle n}$ kutija jednak ${\displaystyle n-m}$ , a to je u kontradikciji s pretpostavkom da želimo smjestiti ${\displaystyle n+1}$ predmet u n kutija, a ${\displaystyle 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 ${\displaystyle |A|}$ broj elemenata skupa ${\displaystyle A}$ . Dirichletov princip može se iskazati i ovako:

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

Vrijedi:

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

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

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 ${\displaystyle r,m\in \mathbb {N} }$ i sve prirodne brojeve ${\displaystyle r_{1},r_{2},...,r_{m}\geq r}$ postoji najmanji prirodni broj ${\displaystyle N=N(r_{1},r_{2},...,r_{m};r)}$ , tako velik da ako imamo skup od ${\displaystyle n}$ elemenata, ${\displaystyle n\geq N}$ i ako u tom skupu razvrstamo sve ${\displaystyle r}$ -podskupove u ${\displaystyle m}$ klasa ${\displaystyle K_{1},K_{2},...,K_{m}}$ onda postoji:

ili ${\displaystyle r_{1}}$ elemenata čiji su svi ${\displaystyle r}$ -podskupovi u klasi ${\displaystyle K_{1}}$ ,

ili ${\displaystyle r_{2}}$ elemenata čiji su svi ${\displaystyle r}$ -podskupovi u klasi ${\displaystyle K_{2}}$ ,

.

.

.

ili ${\displaystyle r_{m}}$ elemenata čiji su svi ${\displaystyle r}$ -podskupovi u klasi ${\displaystyle K_{m}}$ .

Broj ${\displaystyle N(r_{1},r_{2},...,r_{m};r)}$ zove se (opći) Ramseyjev broj.

Za ${\displaystyle 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 ${\displaystyle p}$ vrhova čije su sve spojnice plave ili potpun podgraf s ${\displaystyle q}$ vrhova čije su sve spojnice crvene.