Princip golubinjaka

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web-stranice ili drugi izvori).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.
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.

U matematici i računarstvu Princip golubinjaka ili Dirichletov princip kutija (engl. Pidgeonhole Principle) je princip koji navodi da ako se n golubova u golubinjak od m kutija stavi, gdje je n>m, da onda postoji najmanje jedna kutija u kojoj 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, da ć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[uredi | uredi izvor]

Teorema 1

Neka je prirodan broj. Ako predmeta bilo kako rasporedimo u n kutija (pretinaca), tada bar jedna kutija sadrži bar 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, sigurno vrijedi . Tada će broj kutija koje sadrže jedan predmet biti . To bi značilo da je ukupan broj predmeta smještenih u kutija š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 predmetapogreš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[uredi | uredi izvor]

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[uredi | uredi izvor]

Broj ljudi rođenih u istom mjesecu[uredi | uredi izvor]

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[uredi | uredi izvor]

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[uredi | uredi izvor]

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[uredi | uredi izvor]

Izvor[uredi | uredi izvor]

Reference[uredi | uredi izvor]