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]
![](http://up.wiki.x.io/wikipedia/commons/thumb/5/5c/TooManyPigeons.jpg/220px-TooManyPigeons.jpg)
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
urediNeka 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 forma
urediAko je predmeta razmješteno u kutija, onda barem jedna kutija sadrži predmet.
Ramseyjeva teorija
urediPoopć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 i sve prirodne brojeve postoji najmanji prirodni broj , tako velik da ako imamo skup od elemenata, i ako u tom skupu razvrstamo sve -podskupove u klasa onda postoji:
- ili elemenata čiji su svi -podskupovi u klasi ,
- ili elemenata čiji su svi -podskupovi u klasi ,
- .
- .
- .
- ili elemenata čiji su svi -podskupovi u klasi .
Broj zove se (opći) Ramseyjev broj.
Slučaj kada je
urediZa 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 vrhova čije su sve spojnice plave ili potpun podgraf s vrhova čije su sve spojnice crvene.
Izvori
uredi- ↑ https://hrcak.srce.hr › filePDF Web-rezultati Dirichletov princip