1. Zadatak
U prostoriji se nalazi sedam osoba. Četiri od njih poznaju točno po jednu osobu, a preostale tri osobe poznaju točno po dvije osobe. Sva poznanstva su uzajamna. Kolika je vjerojatnost da se dvije slučajno odabrane osobe međusobno ne poznaju?
Rješenje
Prvo rješenje.
Ukupan broj uređenih parova osoba je
Broj uređenih parova osoba koje se poznaju je
Vjerojatnost da se dvije slučajno odabrane osobe poznaju je
Tražena vjerojatnost iznosi
Drugo rješenje.
Dvije osobe možemo odabrati na
način. U svakom poznanstvu sudjeluju točno dvije osobe, a ukupan broj sudjelovanja osoba u poznanstvima je
Zato je ukupan broj poznanstava . Broj parova osoba koje se ne poznaju je , pa tražena vjerojatnost iznosi
Napomena. Rješenje možemo zapisati koristeći terminologiju iz teorije grafova. Osobe možemo reprezentirati kao vrhove grafa čiji su stupnjevi . Budući da je zbroj stupnjeva vrhova jednak dvostrukom broju bridova, graf mora imati bridova. Vjerojatnost da odaberemo par vrhova koji nisu spojeni bridom je .
Treće rješenje.
Razlikujemo tri slučaja.
i) Svaka osoba koja ima jednog poznanika poznaje osobu koja ima jednog poznanika. Tada su osobe koje imaju jednog poznanika grupirane u dva para, a trojka koja ima po dva poznanika čini treću grupu. Grafički tu situaciju možemo reprezentirati na sljedeći način:
ii) Od osoba koje imaju jednog poznanika dvije se međusobno poznaju, a preostale dvije poznaju po jednu od preostalih triju osoba. Tada imamo jedan par osoba i jednu petorku osoba koje se poznaju. Grafički:
iii) Nijedna osoba koja ima jednog poznanika ne poznaje osobu koja ima jednog poznanika. Tada imamo dvije grupe od po i osobe koje grafički možemo prikazati na sljedeći način:
U svakom od slučajeva broj poznanstava je . Dvije osobe možemo odabrati na način, a broj parova osoba koje se ne poznaju je . Tražena vjerojatnost iznosi