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 [math]\displaystyle{ n }[/math] prirodan broj. Ako [math]\displaystyle{ n+ 1 }[/math] 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 [math]\displaystyle{ n }[/math] kutija sadrži ili jedan ili nijedan predmet. Označimo s [math]\displaystyle{ m }[/math] broj praznih kutija. Vrijedi [math]\displaystyle{ m \ge 0 }[/math]. Tada će broj kutija koje sadrže jedan predmet biti [math]\displaystyle{ n - m }[/math]. To bi značilo da je ukupan broj predmeta smještenih u [math]\displaystyle{ n }[/math] kutija jednak [math]\displaystyle{ n- m }[/math], a to je u kontradikciji s pretpostavkom da želimo smjestiti [math]\displaystyle{ n + 1 }[/math] predmet u n kutija, a [math]\displaystyle{ n - m \le n \lt n + 1 }[/math].

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 [math]\displaystyle{ |A| }[/math] broj elemenata skupa [math]\displaystyle{ A }[/math]. Dirichletov princip može se iskazati i ovako:

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

Vrijedi:

Neka su [math]\displaystyle{ S, T }[/math] konačni skupovi sa [math]\displaystyle{ |S| = |T | = n, a f : S \rightarrow T }[/math] neko preslikavanje. Tada je [math]\displaystyle{ f }[/math] injekcija.

Dirichletov princip — jaka forma

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