Kombinatorika - zadaci - teški zadaci sa rešenjima

Rešenje:
Kolekcija je potpuno određena brojevima [tex]a,b,c,d\ge 0[/tex] kovanica od [tex]1[/tex], [tex]5[/tex], [tex]10[/tex] i [tex]20[/tex] evrocenti, pri čemu je
[tex]a+b+c+d=15[/tex]
Kodirajmo takvu četvorku nizom od [tex]15[/tex] zvezdica i [tex]3[/tex] crte: [tex]a[/tex] zvezdica, crta, [tex]b[/tex] zvezdica, crta, [tex]c[/tex] zvezdica, crta, [tex]d[/tex] zvezdica. To je bijekcija između kolekcija i nizova od [tex]18[/tex] simbola sa tačno [tex]3[/tex] crte, a takav niz je određen mestima crta:
[tex]\binom{18}{3}=\frac{18\cdot 17\cdot 16}{6}=816[/tex]
(To su kombinacije sa ponavljanjem od [tex]4[/tex] elementa klase [tex]15[/tex]: [tex]\binom{4+15-1}{15}=\binom{18}{3}[/tex].)

Rešenje:
Neka je [tex]N\gt 3{,}6\cdot 10^9[/tex] broj ljudi. Najviše [tex]0{,}01N[/tex] njih ima više od [tex]100[/tex] godina, pa ljudi koji nemaju više od [tex]100[/tex] godina ima bar
[tex]0{,}99N\gt 0{,}99\cdot 3{,}6\cdot 10^9=3\,564\,000\,000[/tex]
Starost svakog od njih u navršenim godinama je najviše [tex]100[/tex], tj. svaki od njih je živeo manje od [tex]101[/tex] godine, pa su svi oni rođeni u periodu od [tex]101[/tex] godine koji se završava danas. Period od [tex]101[/tex] godine sadrži najviše [tex]101\cdot 366[/tex] dana, pa njegovo trajanje u sekundama nije veće od
[tex]101\cdot 366\cdot 24\cdot 3600=3\,193\,862\,400[/tex]
Čak i ako uračunamo nepotpune sekunde na oba kraja, taj period obuhvata najviše [tex]3\,193\,862\,401[/tex] različitih sekundi (po satu).
Posmatrajmo te sekunde kao kutije i stavimo svakog od tih ljudi u kutiju sekunde u kojoj je rođen. Ljudi ima više od [tex]3\,564\,000\,000[/tex], a kutija najviše [tex]3\,193\,862\,401[/tex], pa prema Dirihleovom principu u nekoj kutiji postoje bar dve osobe, tj. te dve osobe su rođene u istoj sekundi.

Rešenje:
Reč ima [tex]6[/tex] slova: O i S se javljaju po dva puta, a K i M po jednom. Bez ograničenja broj rasporeda (permutacija sa ponavljanjem) jednak je
[tex]\frac{6!}{2!\cdot 2!}=180[/tex]
Neka je [tex]A[/tex] skup rasporeda u kojima su dva slova O susedna, a [tex]B[/tex] skup onih u kojima su dva slova S susedna. Ako slepimo dva slova O u jedan blok, raspoređujemo [tex]5[/tex] objekata među kojima se S javlja dva puta; analogno za [tex]B[/tex]. Ako su slepljena oba para, raspoređujemo [tex]4[/tex] različita objekta:
[tex]|A|=\frac{5!}{2!}=60,\quad |B|=60,\quad |A\cap B|=4!=24[/tex]
Prema principu uključenja i isključenja, broj „loših“ rasporeda je
[tex]|A\cup B|=60+60-24=96[/tex]
Dakle, traženi broj je [tex]180-96=84[/tex].

Rešenje:
Bez ograničenja, na svakom od šest mesta može stajati bilo koje od tri slova, pa ima [tex]3^6=729[/tex] reči.
Neka su [tex]A_1, A_2, A_3[/tex] skupovi reči u kojima se ne pojavljuje redom prvo, drugo i treće slovo. Tada je [tex]|A_i|=2^6=64[/tex]; za [tex]i\ne j[/tex] skup [tex]A_i\cap A_j[/tex] sadrži samo reč sastavljenu od preostalog slova, tj. [tex]|A_i\cap A_j|=1[/tex]; osim toga, [tex]A_1\cap A_2\cap A_3=\varnothing[/tex].
Prema principu uključenja i isključenja, broj reči u kojima nedostaje bar jedno slovo je
[tex]|A_1\cup A_2\cup A_3|=3\cdot 64-3\cdot 1+0=189[/tex]
Dakle, broj reči koje sadrže sva tri slova je [tex]729-189=540[/tex].

Rešenje:
Pošto je [tex]2187=3^7[/tex], svaka cifra je delilac broja [tex]3^7[/tex]. Cifra [tex]0[/tex] nije moguća (proizvod nije [tex]0[/tex]), pa su jedine moguće cifre [tex]1[/tex], [tex]3[/tex] i [tex]9[/tex] ([tex]27[/tex] nije cifra).
Neka broj sadrži [tex]a[/tex] trojki, [tex]b[/tex] devetki i [tex]5-a-b[/tex] jedinica. Tada je
[tex]3^a\cdot 9^b=3^{a+2b}=3^7\Rightarrow a+2b=7,\quad a+b\le 5[/tex]
Zamenom [tex]a=7-2b[/tex] dobijamo [tex]7-b\le 5[/tex], tj. [tex]b\ge 2[/tex], a iz [tex]a\ge 0[/tex] sledi [tex]b\le 3[/tex].
Slučaj [tex]b=2[/tex], [tex]a=3[/tex]: cifre su [tex]3; 3; 3; 9; 9[/tex] i mogu se poređati na [tex]\frac{5!}{3!\cdot 2!}=10[/tex] načina.
Slučaj [tex]b=3[/tex], [tex]a=1[/tex]: cifre su [tex]9; 9; 9; 3; 1[/tex] i mogu se poređati na [tex]\frac{5!}{3!}=20[/tex] načina.
Nijedna cifra nije [tex]0[/tex], pa svaki raspored daje petocifren broj. Ukupno ima [tex]10+20=30[/tex] takvih brojeva.

Rešenje:
Opšti član je
[tex]T_{k+1}=\binom{n}{k}\left(\sqrt{x}\right)^{n-k}\left(\frac{1}{2\sqrt[4]{x}}\right)^{k}=\frac{1}{2^k}\binom{n}{k}x^{\frac{n-k}{2}-\frac{k}{4}}[/tex]
pri čemu izložilac od [tex]x[/tex] opada kada [tex]k[/tex] raste. Da bi postojala tri člana, potrebno je [tex]n\ge 2[/tex]. Koeficijenti prva tri člana ([tex]k=0; 1; 2[/tex]) su
[tex]1; \quad \frac{n}{2}; \quad \frac{1}{4}\binom{n}{2}=\frac{n(n-1)}{8}[/tex]
Oni obrazuju aritmetički niz tačno onda kada je
[tex]2\cdot \frac{n}{2}=1+\frac{n(n-1)}{8}\iff 8n=8+n^2-n\iff n^2-9n+8=0[/tex]
sa rešenjima [tex]n=1[/tex] i [tex]n=8[/tex]. Rešenje [tex]n=1[/tex] odbacujemo, jer tada razvoj ima samo dva člana. Za [tex]n=8[/tex] koeficijenti su [tex]1; 4; 7[/tex], što zaista jeste aritmetički niz. Dakle, [tex]n=8[/tex].

Rešenje:
Zbog [tex]\lg x[/tex] mora biti [tex]x\gt 0[/tex]. Opšti član razvoja [tex]\left(a+b\right)^5[/tex] je [tex]T_{k+1}=\binom{5}{k}a^{5-k}b^k[/tex]; ovde je [tex]a=x^{\lg x}[/tex], [tex]b=x[/tex], a trećem članu odgovara [tex]k=2[/tex]:
[tex]T_3=\binom{5}{2}\left(x^{\lg x}\right)^3x^2=10\,x^{3\lg x+2}[/tex]
Uslov [tex]T_3=100[/tex] daje [tex]x^{3\lg x+2}=10[/tex]. Obe strane su pozitivne, pa ih možemo logaritmovati za osnovu [tex]10[/tex]:
[tex]\left(3\lg x+2\right)\lg x=1[/tex]
Smenom [tex]u=\lg x[/tex] dobijamo
[tex]3u^2+2u-1=0\Rightarrow u=\frac{1}{3}\text{ ili }u=-1[/tex]
Dakle, [tex]x=10^{\frac{1}{3}}=\sqrt[3]{10}[/tex] ili [tex]x=10^{-1}=\frac{1}{10}[/tex]; obe vrednosti su pozitivne, pa su obe dopustive.
Provera: za [tex]x=\frac{1}{10}[/tex] je [tex]x^{\lg x}=10[/tex] i [tex]T_3=10\cdot 10^3\cdot \frac{1}{100}=100[/tex]; za [tex]x=\sqrt[3]{10}[/tex] je [tex]T_3=10\cdot 10^{\frac{1}{3}}\cdot 10^{\frac{2}{3}}=100[/tex].

Rešenje:
Neparni brojevi zauzimaju neparna mesta, pa parni brojevi [tex]2, 4, 6, 8, 10[/tex] zauzimaju parna mesta [tex]2, 4, 6, 8, 10[/tex] i nijedan od njih ne sme da stoji na svom mestu. Dakle, treba odrediti broj [tex]D_5[/tex] permutacija [tex]5[/tex] elemenata u kojima nijedan element nije na svom mestu.
Primenjujemo princip uključenja i isključenja: [tex]m[/tex] brojeva koji moraju ostati na svojim mestima mogu se izabrati na [tex]\binom{5}{m}[/tex] načina, a preostalih [tex]5-m[/tex] brojeva mogu se rasporediti na [tex](5-m)![/tex] načina. Zato je
[tex]D_5=5!-\binom{5}{1}\cdot 4!+\binom{5}{2}\cdot 3!-\binom{5}{3}\cdot 2!+\binom{5}{4}\cdot 1!-\binom{5}{5}\cdot 0![/tex]
[tex]D_5=120-120+60-20+5-1=44[/tex]

Rešenje:
Zapišimo zbir obrnutim redosledom, koristeći [tex]\binom{n}{k}=\binom{n}{n-k}[/tex]:
[tex]S=(n+1)\binom{n}{0}+n\binom{n}{1}+\ldots+(n+1-k)\binom{n}{k}+\ldots+1\cdot \binom{n}{n}[/tex]
Sabiranjem dva izraza član po član koeficijent uz svako [tex]\binom{n}{k}[/tex] postaje [tex](k+1)+(n+1-k)=n+2[/tex], a prema binomnoj formuli [tex]\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=(1+1)^n=2^n[/tex]:
[tex]2S=(n+2)\left(\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}\right)=(n+2)\cdot 2^n\ \Rightarrow\ S=(n+2)\cdot 2^{n-1}[/tex]

Rešenje:
Uvedimo koordinate tako da tačke budu [tex]\left(x; y\right)[/tex], gde je [tex]x\in\{0; 1; 2; 3; 4\}[/tex], [tex]y\in\{0; 1; 2\}[/tex]. Tri tačke su temena trougla tačno kada nisu kolinearne. Broj svih trojki tačaka je
[tex]\binom{15}{3}=455[/tex]
Od tog broja oduzimamo kolinearne trojke. Trojki u jednom redu ima [tex]3\cdot \binom{5}{3}=30[/tex].
Svaka druga prava nije horizontalna, pa seče svaki red u najviše jednoj tački i kolinearna trojka na njoj ima po jednu tačku iz svakog reda. Pošto su im ordinate [tex]0, 1, 2[/tex], srednja tačka je središte duži koja spaja druge dve, tj. tačke su [tex]\left(a; 0\right), \left(a+d; 1\right), \left(a+2d; 2\right)[/tex], gde je [tex]0\le a\le 4[/tex] i [tex]0\le a+2d\le 4[/tex]. To daje [tex]5[/tex] trojki za [tex]d=0[/tex] (kolone), po [tex]3[/tex] trojke za [tex]d=\pm 1[/tex] i po [tex]1[/tex] trojku za [tex]d=\pm 2[/tex] (slučaj [tex]\left|d\right|\ge 3[/tex] je nemoguć), tj.
[tex]5+2\cdot 3+2\cdot 1=13[/tex]
Dakle, kolinearnih trojki ima [tex]30+13=43[/tex], a broj trouglova je
[tex]455-43=412[/tex]

Rešenje:
Rastavimo osnovu na činioce:
[tex]1+x+\frac{1}{x^2}+\frac{1}{x^3}=(1+x)+\frac{1}{x^3}(x+1)=(1+x)\left(1+x^{-3}\right)[/tex]
Prema tome, izraz je jednak
[tex](1+x)^6\left(1+x^{-3}\right)^6=\left(\sum_{i=0}^{6}\binom{6}{i}x^i\right)\left(\sum_{j=0}^{6}\binom{6}{j}x^{-3j}\right)[/tex]
Proizvod dva člana daje [tex]x^0[/tex] tačno kada je [tex]i=3j[/tex]. Pošto je [tex]0\le i\le 6[/tex], mogući parovi su [tex]\left(i; j\right)=\left(0; 0\right), \left(3; 1\right), \left(6; 2\right)[/tex], pa je slobodni član
[tex]\binom{6}{0}\binom{6}{0}+\binom{6}{3}\binom{6}{1}+\binom{6}{6}\binom{6}{2}=1+20\cdot 6+15=136[/tex]

Rešenje:
Numerišimo horizontalne linije mreže brojevima [tex]0, 1, \ldots, n[/tex] od osnovice naviše. Linija [tex]j[/tex] sadrži [tex]n-j+1[/tex] čvorova, koje numerišemo brojevima [tex]0, 1, \ldots, n-j[/tex] sleva nadesno (čvor [tex]0[/tex] leži na levoj stranici velikog trougla).
Trougao „nagore” stranice [tex]s[/tex] određen je svojim donjim levim temenom. Ako je to čvor [tex]i[/tex] na liniji [tex]j[/tex], onda je donje desno teme čvor [tex]i+s[/tex] na istoj liniji, a gornje teme čvor [tex]i[/tex] na liniji [tex]j+s[/tex]. Trougao leži u mreži tačno kada je
[tex]i+s\le n-j\iff i+j\le n-s, \quad i, j\ge 0[/tex]
Broj takvih parova [tex]\left(i; j\right)[/tex] je [tex]1+2+\ldots+(n-s+1)=\binom{n-s+2}{2}[/tex]. Sabiranjem po [tex]s=1, 2, \ldots, n[/tex] i korišćenjem [tex]\binom{k}{2}=\binom{k+1}{3}-\binom{k}{3}[/tex] (sabirci se uzastopno poništavaju) dobijamo
[tex]N=\binom{n+1}{2}+\binom{n}{2}+\ldots+\binom{2}{2}=\binom{n+2}{3}=\frac{n(n+1)(n+2)}{6}[/tex]

Rešenje:
Svaki napisani broj je delilac broja [tex]64=2^6[/tex], tj. oblika je [tex]2^a[/tex], gde je [tex]a\ge 0[/tex] ceo broj. Niz [tex]2^{a_1}, 2^{a_2}, \ldots, 2^{a_5}[/tex] ima proizvod [tex]64[/tex] tačno kada je
[tex]a_1+a_2+a_3+a_4+a_5=6, \quad a_i\ge 0[/tex]
Svako takvo uređeno rešenje odgovara rasporedu [tex]6[/tex] jedinica i [tex]4[/tex] pregrade u nizu, pa je broj mogućih nizova
[tex]\binom{6+4}{4}=\binom{10}{4}=210[/tex]
Ako izaberemo [tex]4\cdot 210+1=841[/tex] učenika, onda je prema Dirihleovom principu neki niz napisalo bar [tex]5[/tex] od njih.
[tex]840[/tex] učenika nije dovoljno: moguće je da je svaki od [tex]210[/tex] nizova napisalo bar [tex]4[/tex] učenika (za to je potrebno [tex]840\le 999[/tex] učenika), i ako izaberemo tačno po [tex]4[/tex] učenika za svaki niz, među izabranih [tex]840[/tex] nema pet učenika sa istim nizom. Odgovor je [tex]841[/tex].

Rešenje:
Neka kandidat ima [tex]c[/tex] tačnih i [tex]w[/tex] netačnih odgovora, gde je [tex]c, w\ge 0[/tex] i [tex]c+w\le 40[/tex]; tada ima [tex]s=4c-w[/tex] bodova. Za fiksirano [tex]c[/tex] broj [tex]w[/tex] uzima sve vrednosti od [tex]0[/tex] do [tex]40-c[/tex], pa [tex]s[/tex] uzima sve cele vrednosti iz intervala
[tex]\left[5c-40; 4c\right][/tex]
Intervali za [tex]c[/tex] i [tex]c+1[/tex] ne ostavljaju prazninu između sebe tačno kada je [tex]5(c+1)-40\le 4c+1[/tex], tj. [tex]c\le 36[/tex]. Zato vrednosti [tex]c=0, 1, \ldots, 37[/tex] zajedno daju sve cele brojeve od [tex]-40[/tex] do [tex]4\cdot 37=148[/tex], tj. [tex]189[/tex] rezultata. Preostale vrednosti [tex]c[/tex] daju
[tex]c=38:\ 150, 151, 152\qquad c=39:\ 155, 156\qquad c=40:\ 160[/tex]
Rezultati [tex]149, 153, 154, 157, 158, 159[/tex] su nemogući, pa je broj mogućih rezultata
[tex]189+3+2+1=195[/tex]
Kod [tex]390=2\cdot 195[/tex] kandidata može se desiti da svaki mogući rezultat ostvare tačno dva kandidata, pa nikoja tri kandidata nemaju jednak broj bodova. Kod [tex]391\gt 2\cdot 195[/tex] kandidata, prema Dirihleovom principu, neki rezultat ostvaruju bar tri kandidata. Odgovor je [tex]391[/tex].