Dirichletov princip

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.[1]

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.

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 formaUredi

Neka je   prirodan broj. Ako   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   kutija sadrži ili jedan ili nijedan predmet. Označimo s   broj praznih kutija. Vrijedi  . Tada će broj kutija koje sadrže jedan predmet biti  . To bi značilo da je ukupan broj predmeta smještenih u   kutija jednak  , a to je u kontradikciji s pretpostavkom da želimo smjestiti   predmet u n kutija, a  .

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   broj elemenata skupa  . Dirichletov princip može se iskazati i ovako:

Neka su   i   konačni skupovi, takvi da je  , a   neko preslikavanje. Tada   nije injekcija, tj. postoje  ,  , takvi da je  .

Vrijedi:

Neka su   konačni skupovi sa   neko preslikavanje. Tada je   injekcija.

Dirichletov princip — jaka formaUredi

Ako je   predmeta razmješteno u   kutija, onda barem jedna kutija sadrži   predmet.

IzvoriUredi

  1. https://hrcak.srce.hr › filePDF Web-rezultati Dirichletov princip