Prijemni ispit FON – 29. jun 2006.
17. zadatak

Neka je [inlmath]X[/inlmath] skup svih četvorocifrenih brojeva čije cifre pripadaju skupu [inlmath]\{1,2,3\}[/inlmath], pri čemu se svaka cifra u svakom broju pojavljuje bar jednom. Broj svih podskupova skupa [inlmath]X[/inlmath] je:
Tačan odgovor je pod [inlmath]C)\;2^{5^2}[/inlmath], ovde sam došao do približnog rešenja [inlmath]2\left(2^{26}-1\right)[/inlmath], prvo sam sagledao sve moguće kombinacije u kojem se dva puta jedna cifra mora ponavljati i takvih dobijem [inlmath]9\cdot3=27[/inlmath].
Zatim pošto sam zaključio da ima [inlmath]27[/inlmath] brojeva skup [inlmath]X[/inlmath], išao sam logikom da podskup može sadržati i jedan element od čitavog skupa pa sam rekao,
[inlmath]{27\choose1}+{27\choose2}+{27\choose3}+\cdots+{27\choose26}=2\left(2^{26}-1\right)[/inlmath] posle primene formule da je [inlmath]2^n={n\choose0}+{n\choose1}+{n\choose2}+\cdots+{n\choose n}[/inlmath]. Gde sam mogao da napravim propust?

Čini mi se da si, zbog loše kopije zadataka, pogrešno pročitao broj koji je naveden u odgovoru pod C. Mislim da treba da bude [inlmath]C)\;2^{6^2}[/inlmath].
Napisao si da skup [inlmath]X[/inlmath] ima [inlmath]27[/inlmath] elemenata a to nije tačno. Pošto svaka cifra iz skupa [inlmath]\{1,2,3\}[/inlmath] mora da se pojavi bar jednom, to znači da se sve te cifre pojavljuju u broju, a pošto je broj četvorocifren neka od cifara se pojavljuje dva puta. Ako se jedinica pojavljuje dva puta onda broj ima cifre [inlmath]1,1,2,3[/inlmath]. Izračunaj koliko brojeva možemo napisati pomoću tih cifara (permutacije sa ponavljanjem). A pošto tih mogućnosti nije mnogo, možeš ih i ispisati pa prebrojati. Koliko će biti brojeva ako se dvojka pojavljuje dva puta? ...Koliko će ih biti ukupno.
I još nešto. Kažeš da si "išao logikom da podskup može sadržati i jedan element od čitavog skupa". Međutim, podskup može da sadrži i nula elemenata, odnosno da bude prazan. Drugim rečima, prazan skup je podskup svakog skupa (pa i praznog skupa). Iz toga sledi da skup sa [inlmath]n[/inlmath] elemenata ima [inlmath]2^n[/inlmath] podskupova.

Hvala, ovo za podskup da može sadržati [inlmath]0[/inlmath] elemenata nisam znao. Pokušaću da ga rešim.

Odradio sam zadatak još jednom i došao sam do zaključka da skup [inlmath]H[/inlmath] ima [inlmath]36[/inlmath] brojeva a ne [inlmath]27[/inlmath], i sad ako bih rekao [inlmath]{36\choose 0} +
{36\choose 1} + {36\choose 2} + ... + {36\choose 36} = 2^{36}= 2^{6^2}[/inlmath], jedino sto me jos muči [inlmath]{36\choose 36}[/inlmath] zar se onda ne svodi
da ja sabiram i čitav skup da je mogući podskup ? Ako bih izbacio tj . rekao [inlmath]2^{36} - {36\choose 36}[/inlmath] dobio bih [inlmath]2^{36} - 1[/inlmath]
što opet nije rešenje.

Miloše, u poslednjoj rešenici prethodnog posta sam napisao da skup sa [inlmath]n[/inlmath] elemenata ima [inlmath]2^n[/inlmath] podskupova.
A ti kažeš:

... jedino sto me jos muči [inlmath]{36\choose 36}[/inlmath] zar se onda ne svodi
da ja sabiram i čitav skup da je mogući podskup? Ako bih izbacio tj. rekao [inlmath]2^{36} - {36\choose 36}[/inlmath] dobio bih [inlmath]2^{36} - 1[/inlmath]
što opet nije rešenje.

Izbacio si iz skupa svih podskupova skupa [inlmath]H[/inlmath], " čitav skup ",odnosno skup [inlmath]H[/inlmath], a to je pogrešno. Jedno od prvih (i najosnovnijih) tvrđenja u teoriji skupova jeste tvrđenje koje kaže da je svaki skup podskup samom sebi. Relacija "podskup" je ( kao i relacija " [inlmath]\le[/inlmath] " u skupu realnih brojeva ) relacija poretka, dakle ona je i refleksivna. To znači da je za svaki skup [inlmath]S[/inlmath] tačno tvrđenje [inlmath]S\subseteq S[/inlmath] (kao što je za svaki realan broj [inlmath]x[/inlmath] tačno tvrđenje da je [inlmath]x\le x[/inlmath] ).
Napominjem ti, a to ti je i Daniel rekao (u toj poruci ti je naveo i link), da pogledaš poruku - tekst o skupovima. Teorija skupova je osnovna matematička disciplina. Koriste je sve grane matematike (i zbog toga je proveravaju na prijemnim ispitima).

Miloš je napisao:i sad ako bih rekao [inlmath]{36\choose0}+{36\choose1}+{36\choose2}+\cdots+{36\choose36}=2^{36}=2^{6^2}[/inlmath],

Tvrdnja da skup od [inlmath]n[/inlmath] elemenata ima [inlmath]2^n[/inlmath] različitih podskupova može se dokazati i bez binomnih koeficijenata, na sledeći način.
U svakom od poskupova, svaki od [inlmath]n[/inlmath] elemenata može ili da se pojavljuje ili da se ne pojavljuje. Treće nema, logično.
Znači, za prvi element skupa imamo te dve mogućnosti, pa za drugi isto imamo dve mogućnosti... I tako do [inlmath]n[/inlmath]-tog elementa, za koji takođe imamo dve mogućnosti. To je ukupno [inlmath]\underbrace{2\cdot2\cdots2}_{n\text{ množenja}}=2^n[/inlmath] mogućnosti za formiranje jednog od podskupova. To znači, ima ukupno [inlmath]2^n[/inlmath] različitih tj. mogućih podskupova.
(Ovaj način, zapravo, predstavlja upotrebu varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]n[/inlmath]-te klase.)

Sad je jasno, hvala.