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).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. 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.

Primjeri[uredi | uredi izvor]

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]

Reference[uredi | uredi izvor]