Prijemni ispit FON – 30. jun 2004.
19. zadatak

Različitih petocifrenih brojeva koji imaju tačno dve različite cifre ima:
Tacan odgovor je pod [inlmath]A)\;1215[/inlmath]

Sve sam pokušao i nikako da dođem do rešenja, bio sam i određivao mogućnosti da se pojave brojevi samo u poretku [inlmath]10000[/inlmath], [inlmath]20000[/inlmath], itd, sve uslove koji su mi pali napamet i ništa.

Pošto u broju cifra nula ne može da bude na prvoj poziciji (broj ne bi bio petocifren) razbijemo skup traženih brojeva na dva disjunktna podskupa. U jednom će biti brojevi u kojima se nula ne pojavljuje, a u drugom oni koji imaju nulu. Kad izračunamo koliko elemenata ima u tim skupovima, traženi rezultat ćemo dobiti sabiranjem tih kardinalnih brojeva.
Ako se nula ne pojavljuje, koristićemo tačno dve cifre iz skupa [inlmath]S=\{1,2,3,\ldots,8,9\}[/inlmath]. Te dve cifre možemo iz skupa [inlmath]S[/inlmath] odabrati na [inlmath]9\choose2[/inlmath] načina. Treba još izračunati koliko svaka od tih kombinacija generiše petocifrenih brojeva. Pošto broj mora da sadrži obe cifre, svaka od njih mora da se pojavi bar jednom, a najviše četiri puta (zajedno pet), pa imamo sledeće mogućnosti [inlmath]\{c_1,c_2,c_2,c_2,c_2\}[/inlmath], [inlmath]\{c_1,c_1,c_2,c_2,c_2\}[/inlmath], [inlmath]\{c_1,c_1,c_1,c_2,c_2\}[/inlmath], [inlmath]\{c_1,c_1,c_1,c_1,c_2\}[/inlmath]. Koliko brojeva možemo dobiti razmeštanjem cifara u svakoj od mogućnosti računamo koristeći permutacije sa ponavljanjem....
Ako se nula pojavljuje, osim nje ćemo koristiti još jednu cifru iz skupa [inlmath]S[/inlmath] koju možemo odabrati na [inlmath]9[/inlmath] načina. Dalje postupamo slično kao u prethodnom slučaju. Razlika je u tome što na prvoj poziciji mora da bude odabrana cifra iz [inlmath]S[/inlmath] a ne nula (da bi broj bio petocifren). A za preostale četiri pozicije imamo sledeće kombinacije cifara [inlmath]\{0,0,0,0\}[/inlmath], [inlmath]\{0,0,0,c\}[/inlmath], [inlmath]\{0,0,c,c\}[/inlmath], [inlmath]\{0,c,c,c\}[/inlmath]....

Način s permutacijama s ponavljanjem je sasvim OK, mada bih ja prednost dao načinu preko varijacija s ponavljanjem.

• Ako se nula ne pojavljuje, nakon što na neki od [inlmath]9\choose2[/inlmath] načina odaberemo dve nenulte cifre, broj načina na koje te dve cifre raspoređujemo na [inlmath]5[/inlmath] pozicija iznosi [inlmath]\overline V_2^5=2^5[/inlmath]. Od toga sad treba oduzeti slučaj kod kojeg je jedna od te dve cifre na svih [inlmath]5[/inlmath] pozicija, kao i slučaj kod kojeg je druga od te dve cifre na svih [inlmath]5[/inlmath] pozicija. Znači, [inlmath]2^5-2=30[/inlmath].
• Slično i za slučaj kada se nula pojavljuje, samo što ovde od broja varijacija s ponavljanjem treba oduzeti samo jedan slučaj (kada je ona nenulta cifra na svih [inlmath]5[/inlmath] pozicija).