Princip golubinjaka

U matematici i računarstvu Princip golubinjaka ili Dirichletov princip kutija (engl. Pigeonhole Principle) je princip koji 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.

Prvu formalizaciju ove ideje je vjerovatno napravio Johann Dirichlet 1834. godine pod imenom Schubfachprinzip.

 Dirichletov princip— slaba forma 
Teorema 1

Neka je  prirodan broj. Ako  predmeta bilo kako rasporedimo u n kutija (pretinaca), tada barem jedna kutija sadrži barem dva predmeta.

Dokaz

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

Teorema 2

Neka su S i T konačni skupovi, takvi da je , a f : S → T neko preslikavanje. Tada f nije injekcija, tj. postoje x, x' ∈ S, , takvi da je f(x)= f(x').

Teorema 3

Neka su S i T konačni skupovi sa |S| = |T | = n, a f : S → T neko preslikavanje. Tada je f injekcija <=> f surjekcija.
 Dirichletov princip— jaka forma 

Ako je  predmeta razmješteno u  kutija, onda barem jedna kutija
sadrži 	 predmet, gdje je   funkcija koja realnom broju x pridružuje najveći cijeli broj koji nije veći od x.
 Primjeri 
Broj ljudi rođenih u istom mjesecu
Među 77 ljudi barem je 7 rođeno u istom mjesecu.

Rješenje:

Koristeći se jakom formom Dirichletova principa, slijedi da je barem 

ljudi rođeno u istom mjesecu.

 Broj dlaka na glavi 
Moguće je demonstrirati da postoje najmanje dvoje ljudi u Londonu sa istim brojem dlaka na glavi na sljedeći način. Tipična osoba ima oko 150.000 dlaka na glavi, tako da je razumno reći da niko nema više od 1.000.000 dlaka na glavi (m=1 milion skupova). U Londonu ima više od 1.000.000 ljudi (n>1.000.000) koji se mogu rasporediti u m skupova (m<n) - svaki skup po mogućem broju dlaka na glavi. To znači da postoji najmanje jedan skup u kojem je raspoređeno najmanje dvoje ljudi, ili ekvivalentno, postoje najmanje dvoje ljudi sa istim brojem dlaka na glavi.

 Paradoks rođendana 
Paradoks rođendana se odnosi na vjerovatnoću da iz skupa od n slučajno izabranih ljudi dvoje ljudi imaju isti rođendan. Sa principom golubnjika može se dokazati da je sa n=367 ljudi ova vjerovatnoća 100%, i to na sljedeći način. Ukupni broj rođendana je m=366 (uključujući 29. Februar) tako da u tom slučaju mora postojati najmanje jedan skup od dvoje ljudi koji imaju isti rođendan.

 Također pogledajte 
 Kombinatoriski principi
 Dedekind-bezkrajni skup
 Hilbertov paradoks velikog hotela
 Multinomna teorema
 Ramseyova teorema
 Kombinatorijski dokaz
Izvor
Princip golubinjaka/Snježana Majstorović /Osječki matematički list  6(2006), 99–105
The strange case of The Pigeon-hole Principle/27. maj 2010.

 Reference 
  Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. . str. 244–248.
  Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics  (engl.). Elektronski dokument, primljen 11. Novembra, 2006.

Kategorija:Kombinatorika
Kategorija:Teorije u diskretnoj matematici
Kategorija:Matematički principi
Kategorija:Ramseyova teorija