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.

Fotografija golubova u kutijama. U ovom primjeru imaju n = 10 golubova u m = 9 kutija, tako da po *principu golubinjaka*, najmanje jedna kutija ima više od jednog 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 $n$ prirodan broj. Ako $n+1$ 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 $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:

Teorema 2

Neka su S i T konačni skupovi, takvi da je $|S|>|T|$ , a f : S → T neko preslikavanje. Tada f nije injekcija, tj. postoje x, x' ∈ S, $x'\neq x$ , 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 $m$ predmeta razmješteno u $n$ kutija, onda barem jedna kutija sadrži $\left\lfloor {\frac {m-1}{n}}\right\rfloor +1$ predmet, gdje je $x\to l\left\lfloor x\right\rfloor$ 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 $\left\lfloor {\frac {77-1}{12}}\right\rfloor +1=\left\lfloor 6,3\right\rfloor +1=7$ 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

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

(en) Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. str. 244–248.
(en) 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.