Kombinatorika - zadaci - zadaci sa rešenjima

Rešenje:
Svaki od pet učenika raspoređuje se u tačno jedno od tri odeljenja nezavisno od ostalih, a raspored je potpuno određen odeljenjem svakog učenika. Po principu proizvoda broj rasporeda je
[tex]3\cdot 3\cdot 3\cdot 3\cdot 3=3^5=243[/tex]

Rešenje:
Redosled igrača unutar svake grupe nije bitan, pa brojimo kombinacije. Broj načina da se izaberu golman, dva odbrambena igrača i tri napadača je redom
[tex]\binom{2}{1}=2,\qquad \binom{6}{2}=15,\qquad \binom{8}{3}=56[/tex]
Ovi izbori su nezavisni, pa je po principu proizvoda broj postava
[tex]2\cdot 15\cdot 56=1680[/tex]

Rešenje:
Cifra [tex]0[/tex] ne može da se pojavi: bila bi najmanja cifra, pa bi morala da stoji na prvom mestu, što je nemoguće za sedmocifren broj. Dakle, sve cifre su među [tex]1,2,\dots,9[/tex].
Obrnuto, svaki izbor [tex]7[/tex] različitih cifara iz [tex]1,2,\dots,9[/tex] daje tačno jedan takav broj — izabrane cifre napisane u rastućem poretku. Zato je traženi broj jednak broju načina da se izabere [tex]7[/tex] cifara od [tex]9[/tex]:
[tex]\binom{9}{7}=\binom{9}{2}=\frac{9\cdot 8}{2}=36[/tex]

Rešenje:
Razmatramo slučajeve prema mestu jedine cifre [tex]3[/tex]. Ako je to cifra stotina, cifre desetica i jedinica mogu biti bilo koja od [tex]9[/tex] cifara različitih od [tex]3[/tex]:
[tex]9\cdot 9=81[/tex]
Ako je to cifra desetica, cifra stotina ne može biti [tex]0[/tex] ni [tex]3[/tex] ([tex]8[/tex] mogućnosti), a cifra jedinica je bilo koja cifra osim [tex]3[/tex] ([tex]9[/tex] mogućnosti):
[tex]8\cdot 9=72[/tex]
Ako je to cifra jedinica, analogno dobijamo
[tex]8\cdot 9=72[/tex]
Slučajevi se ne preklapaju, pa je broj takvih brojeva
[tex]81+72+72=225[/tex]

Rešenje:
Reč ima [tex]10[/tex] slova: M se javlja [tex]2[/tex] puta, A [tex]3[/tex] puta, T [tex]2[/tex] puta, a E, I i K po jednom. Kada bi sva slova bila različita, mogla bi da se poređaju na [tex]10![/tex] načina.
Međusobna zamena jednakih slova ne menja reč, pa je svaka reč među ovim rasporedima prebrojana tačno [tex]2!\cdot 3!\cdot 2!=24[/tex] puta. Dakle, broj različitih reči je
[tex]\frac{10!}{2!\cdot 3!\cdot 2!}=\frac{3628800}{24}=151200[/tex]

Rešenje:
Tri tačke su temena trougla tačno onda kada nisu kolinearne. Zato sva tri temena ne mogu biti na istoj od datih pravih, tj. trougao ima dva temena na jednoj pravoj i jedno teme na drugoj. Obrnuto, svaka takva trojka tačaka daje trougao, jer treća tačka ne leži na pravoj kroz preostale dve (prave su paralelne i različite).
Dva temena na pravoj sa [tex]10[/tex] tačaka i jedno na drugoj pravoj:
[tex]\binom{10}{2}\cdot 20=45\cdot 20=900[/tex]
Dva temena na pravoj sa [tex]20[/tex] tačaka i jedno na drugoj pravoj:
[tex]\binom{20}{2}\cdot 10=190\cdot 10=1900[/tex]
Ova dva slučaja se ne preklapaju, pa je ukupan broj trouglova
[tex]900+1900=2800[/tex]

Rešenje:
Bitno je ko ide u koji grad, pa brojimo uređene trojke različitih zaposlenih izabranih od svih [tex]9[/tex] (varijacije). Bez ograničenja njihov broj je
[tex]9\cdot 8\cdot 7=504[/tex]
Nedozvoljeni su izbori bez ekonomiste, tj. kada su sva trojica koji putuju pravnici:
[tex]5\cdot 4\cdot 3=60[/tex]
Svaki drugi izbor sadrži bar jednog ekonomistu, pa je traženi broj
[tex]504-60=444[/tex]

Rešenje:
Prema binomnoj formuli, opšti član razvoja je
[tex]T_{k+1}=\binom{7}{k}\left(2x^{4}\right)^{7-k}\left(\frac{1}{x^{3}}\right)^{k}=\binom{7}{k}\cdot 2^{7-k}\cdot x^{28-7k},\qquad k=0,1,\dots,7[/tex]
Član ne sadrži [tex]x[/tex] tačno onda kada je [tex]28-7k=0[/tex], tj. [tex]k=4[/tex]. Dakle, slobodan član je
[tex]T_{5}=\binom{7}{4}\cdot 2^{3}=35\cdot 8=280[/tex]

Rešenje:
Izraza ima [tex]2^4=16[/tex], ali različiti izrazi mogu imati jednake vrednosti, pa direktno brojimo vrednosti. Neka je [tex]S[/tex] zbir brojeva ispred kojih stoji znak minus. Tada je vrednost izraza
[tex](2+4+6+8)-2S=20-2S[/tex]
Dakle, različitim vrednostima [tex]S[/tex] odgovaraju različite vrednosti izraza i obrnuto. Pišemo [tex]S=2T[/tex], gde je [tex]T[/tex] zbir nekih od brojeva [tex]1; 2; 3; 4[/tex] (moguće nijednog od njih). Svaki ceo broj od [tex]0[/tex] do [tex]10[/tex] je takav zbir:
[tex]0; 1; 2; 3; 4; 5=1+4; 6=2+4; 7=3+4; 8=1+3+4; 9=2+3+4; 10=1+2+3+4[/tex]
Drugih vrednosti nema, jer je [tex]0\le T\le 10[/tex]. Dakle, vrednost izraza [tex]20-4T[/tex] uzima tačno [tex]11[/tex] različitih vrednosti:
[tex]-20; -16; -12; \dots; 16; 20[/tex]

Rešenje:
Najpre poređamo u niz [tex]8[/tex] crvenih olovaka; pošto su jednake, to je moguće na samo jedan način. One obrazuju [tex]9[/tex] mesta za plave olovke: [tex]7[/tex] razmaka između susednih crvenih olovaka i [tex]2[/tex] mesta na krajevima.
Dve plave olovke su susedne tačno onda kada su stavljene na isto mesto, pa plave olovke moraju zauzeti [tex]4[/tex] različita mesta od ovih [tex]9[/tex]. Plave olovke su jednake, pa je bitno samo koja su mesta izabrana, i svaki dozvoljeni raspored se dobija tačno jednom:
[tex]\binom{9}{4}=\frac{9\cdot 8\cdot 7\cdot 6}{4!}=126[/tex]

Rešenje:
Figura treba da se pomeri za [tex]7[/tex] kolona udesno i za [tex]7[/tex] redova nagore. Svaki potez menja ili kolonu ili red za [tex]1[/tex], pa je potrebno najmanje [tex]14[/tex] poteza, a [tex]14[/tex] poteza je dovoljno.
Put od [tex]14[/tex] poteza ne može sadržati potez ulevo ili nadole: takav potez bi morao da se nadoknadi dodatnim potezom udesno ili nagore, pa bi put bio duži od [tex]14[/tex] poteza.
Dakle, najkraći putevi su tačno nizovi od [tex]7[/tex] poteza „udesno“ i [tex]7[/tex] poteza „nagore“ u nekom poretku (svaki od njih ostaje na tabli). Takav niz je određen izborom koja su [tex]7[/tex] od [tex]14[/tex] poteza „udesno“:
[tex]\binom{14}{7}=3432[/tex]