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, ukoliko 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.