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

Rešenje:
Svaki prirodan broj se na jedinstven način zapisuje u obliku [tex]2^k m[/tex], gde je [tex]k\ge 0[/tex] ceo broj, a [tex]m[/tex] neparan broj; [tex]m[/tex] zovemo neparnim delom tog broja.
Neparni deo broja iz skupa [tex]\{1; 2; \ldots; 2n\}[/tex] nije veći od samog broja, pa je to jedan od [tex]n[/tex] neparnih brojeva [tex]1, 3, 5, \ldots, 2n-1[/tex].
Izabrano je [tex]n+1[/tex] brojeva, a mogućih neparnih delova ima samo [tex]n[/tex], pa prema Dirihleovom principu dva izabrana broja, recimo [tex]a\lt b[/tex], imaju isti neparni deo [tex]m[/tex]:
[tex]a=2^k m, \quad b=2^l m, \quad a\lt b\ \Rightarrow\ k\lt l\ \Rightarrow\ b=2^{l-k}\cdot a[/tex]
Dakle, [tex]a[/tex] deli [tex]b[/tex], čime je tvrđenje dokazano.

Rešenje:
Neka su dati brojevi [tex]a_1\lt a_2\lt \ldots\lt a_{102}[/tex], svi iz skupa [tex]\{1; 2; \ldots; 200\}[/tex]. Posmatrajmo [tex]101[/tex] broj
[tex]a_2-a_1, a_3-a_1, \ldots, a_{102}-a_1[/tex]
koji su međusobno različiti i nalaze se između [tex]1[/tex] i [tex]199[/tex], kao i [tex]101[/tex] broj
[tex]a_2, a_3, \ldots, a_{102}[/tex]
koji su međusobno različiti i nalaze se između [tex]2[/tex] i [tex]200[/tex]. Ukupno je to [tex]202[/tex] broja iz skupa sa samo [tex]200[/tex] elemenata, pa su prema Dirihleovom principu dva od njih jednaka. Ti brojevi ne mogu biti iz iste grupe, jer su u svakoj grupi brojevi različiti. Dakle, za neke [tex]i, j\in\{2; 3; \ldots; 102\}[/tex] važi
[tex]a_i-a_1=a_j\ \Rightarrow\ a_1=a_i-a_j[/tex]
Pri tome je [tex]i\ne j[/tex], jer iz [tex]a_1\gt 0[/tex] sledi [tex]a_i\gt a_j[/tex], a [tex]a_i[/tex] i [tex]a_j[/tex] su različiti od [tex]a_1[/tex], jer je [tex]i, j\ge 2[/tex]. Dakle, najmanji broj [tex]a_1[/tex] jednak je razlici dva druga od datih brojeva.

Rešenje:
Zapišimo svaki takav broj sa tačno pet cifara, dopisujući po potrebi nule ispred: [tex]n=\overline{d_1d_2d_3d_4d_5}[/tex]. To je obostrano jednoznačna korespondencija između brojeva [tex]0\le n\lt 10^5[/tex] i uređenih petorki cifara, a nule ispred ne menjaju zbir cifara. Dakle, brojimo cela rešenja
[tex]d_1+d_2+d_3+d_4+d_5=12,\qquad 0\le d_i\le 9[/tex]
Bez gornjeg ograničenja [tex]d_i\le 9[/tex] broj rešenja u nenegativnim celim brojevima je (metod „zvezdica i crtica“: [tex]12[/tex] zvezdica i [tex]4[/tex] crtice)
[tex]\binom{16}{4}=1820[/tex]
Sada uklanjamo rešenja u kojima je neka cifra bar [tex]10[/tex]. Dve cifre ne mogu istovremeno biti bar [tex]10[/tex], jer je [tex]10+10\gt 12[/tex], pa se ti slučajevi ne preklapaju. Ako je, na primer, [tex]d_1\ge 10[/tex], stavimo [tex]d_1=10+e_1[/tex], gde je [tex]e_1\ge 0[/tex]; tada je [tex]e_1+d_2+d_3+d_4+d_5=2[/tex], što ima [tex]\binom{6}{4}=15[/tex] rešenja. Isto važi za svaku od [tex]5[/tex] pozicija, pa je broj nedozvoljenih rešenja
[tex]5\cdot 15=75[/tex]
Prema tome, traženi broj je
[tex]1820-75=1745[/tex]

Rešenje:
Broj reči sa tačno [tex]k[/tex] slova [tex]a[/tex] je [tex]\binom{n}{k}3^{n-k}[/tex]: biramo [tex]k[/tex] pozicija slova [tex]a[/tex], a na svakoj od ostalih [tex]n-k[/tex] pozicija stoji jedno od slova [tex]b, c, d[/tex].
Neka su [tex]E_n[/tex] i [tex]O_n[/tex] redom brojevi reči sa parnim i sa neparnim brojem slova [tex]a[/tex]. Prema binomnoj formuli
[tex]E_n+O_n=\sum_{k=0}^{n}\binom{n}{k}3^{n-k}=(3+1)^n=4^n[/tex]
[tex]E_n-O_n=\sum_{k=0}^{n}\binom{n}{k}(-1)^k3^{n-k}=(3-1)^n=2^n[/tex]
Oduzimanjem ovih jednakosti dobijamo
[tex]2O_n=4^n-2^n\Rightarrow O_n=\frac{4^n-2^n}{2}[/tex]
Provera: za [tex]n=1[/tex] dobijamo [tex]1[/tex] (reč [tex]a[/tex]); za [tex]n=2[/tex] dobijamo [tex]6[/tex] (reči [tex]ab, ac, ad, ba, ca, da[/tex]).

Rešenje:
Treba izabrati [tex]5[/tex] od [tex]12[/tex] mesta raspoređenih u krug tako da nikoja dva izabrana mesta ne budu susedna.
Lema. Od [tex]m[/tex] objekata poređanih u niz može se izabrati [tex]k[/tex] po dva nesusednih objekata na [tex]\binom{m-k+1}{k}[/tex] načina. Zaista, [tex]m-k[/tex] neizabranih objekata obrazuje [tex]m-k+1[/tex] praznina (uključujući oba kraja), a izbor bez susednih objekata odgovara tačno smeštanju [tex]k[/tex] izabranih objekata u [tex]k[/tex] različitih praznina, najviše po jedan u svaku.
Numerišimo vitezove oko stola brojevima [tex]1; 2; \ldots; 12[/tex]. Slučaj 1: vitez [tex]1[/tex] je izabran. Tada vitezovi [tex]2[/tex] i [tex]12[/tex] ne mogu biti izabrani, pa treba izabrati [tex]4[/tex] po dva nesusedna viteza među [tex]3; 4; \ldots; 11[/tex]. Tih [tex]9[/tex] vitezova obrazuje niz (nijedan od njih nije sused viteza [tex]1[/tex], a vitezovi [tex]3[/tex] i [tex]11[/tex] nisu susedi), pa je prema lemi broj načina
[tex]\binom{9-4+1}{4}=\binom{6}{4}=15[/tex]
Slučaj 2: vitez [tex]1[/tex] nije izabran. Tada biramo [tex]5[/tex] po dva nesusednih vitezova među [tex]2; 3; \ldots; 12[/tex]. Tih [tex]11[/tex] vitezova obrazuje niz, jer su vitezovi [tex]2[/tex] i [tex]12[/tex] razdvojeni vitezom [tex]1[/tex], pa je broj načina
[tex]\binom{11-5+1}{5}=\binom{7}{5}=21[/tex]
Ovi slučajevi se ne preklapaju, pa je odgovor
[tex]15+21=36[/tex]

Rešenje:
Uvedimo koordinate tako da Kermit polazi iz [tex]\left(0; 0\right)[/tex]. On pravi tačno [tex]100[/tex] skokova i svaki skok menja jednu od koordinata za [tex]\pm 1[/tex].
Svaki skok menja [tex]|x|+|y|[/tex] najviše za [tex]1[/tex], pa je na kraju [tex]|x|+|y|\le 100[/tex]. Svaki skok menja [tex]x+y[/tex] za [tex]\pm 1[/tex], tj. menja mu parnost; posle parnog broja skokova broj [tex]x+y[/tex], a time i [tex]|x|+|y|[/tex], je paran.
Obrnuto, svaki čvor sa [tex]d=|x|+|y|\le 100[/tex] i parnim [tex]d[/tex] je dostižan: Kermit napravi [tex]|x|[/tex] horizontalnih i [tex]|y|[/tex] vertikalnih skokova prema njemu, a zatim preostalih [tex]100-d[/tex] džula (paran broj) potroši tako što [tex]\frac{100-d}{2}[/tex] puta skoči na istok i nazad na zapad.
Za [tex]d\ge 1[/tex] postoji tačno [tex]4d[/tex] čvorova sa [tex]|x|+|y|=d[/tex], a za [tex]d=0[/tex] jedan čvor. Stavljajući [tex]d=2t[/tex], dobijamo broj mogućih čvorova:
[tex]1+\sum_{t=1}^{50}4\cdot 2t=1+8\cdot \frac{50\cdot 51}{2}=1+10200=10201=101^2[/tex]

Rešenje:
Polinom je
[tex]P(x)=\sum_{k=0}^{100}x^{k}(1+x)^{100-k}[/tex]
Koristimo identitet [tex]a^{n}-b^{n}=(a-b)\left(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1}\right)[/tex] za [tex]a=1+x[/tex], [tex]b=x[/tex], [tex]n=101[/tex]. Pošto je [tex]a-b=1[/tex], drugi činilac je tačno [tex]P(x)[/tex], pa je
[tex]P(x)=(1+x)^{101}-x^{101}[/tex]
Član [tex]x^{101}[/tex] ne utiče na koeficijent uz [tex]x^{50}[/tex], pa je prema binomnoj formuli taj koeficijent [tex]\binom{101}{50}[/tex].
Provera na drugi način: za [tex]k\le 50[/tex] koeficijent uz [tex]x^{50}[/tex] u [tex]x^{k}(1+x)^{100-k}[/tex] je [tex]\binom{100-k}{50-k}=\binom{100-k}{50}[/tex] (za [tex]k\gt 50[/tex] on je [tex]0[/tex]), a prema identitetu [tex]\sum_{m=r}^{N}\binom{m}{r}=\binom{N+1}{r+1}[/tex]
[tex]\sum_{m=50}^{100}\binom{m}{50}=\binom{101}{51}=\binom{101}{50}[/tex]

Rešenje:
Proste cifre su [tex]2; 3; 5; 7[/tex] (četiri cifre); ostalih šest cifara [tex]0; 1; 4; 6; 8; 9[/tex] nisu proste. Sedmocifrenih brojeva ima [tex]9\cdot 10^6=9\,000\,000[/tex], pa brojimo komplement: brojeve u kojima nema dve susedne proste cifre.
Za [tex]k=1; 2; \ldots; 7[/tex] neka su [tex]p_k[/tex] i [tex]q_k[/tex] brojevi dozvoljenih početaka dužine [tex]k[/tex] (prva cifra različita od nule, bez dve susedne proste cifre) koji se završavaju redom prostom i neprostom cifrom, i neka je [tex]T_k=p_k+q_k[/tex]. Za prvu cifru (nenulte neproste cifre su [tex]1; 4; 6; 8; 9[/tex])
[tex]p_1=4,\qquad q_1=5,\qquad T_1=9[/tex]
Prosta cifra može da sledi samo posle neproste cifre, a neprosta cifra posle bilo koje cifre, pa je
[tex]p_{k+1}=4q_k,\qquad q_{k+1}=6T_k[/tex]
Tada je [tex]T_2=4\cdot 5+6\cdot 9=74[/tex], a za [tex]k\ge 2[/tex]
[tex]T_{k+1}=6T_k+4q_k=6T_k+24T_{k-1}[/tex]
Prema tome,
[tex]T_3=6\cdot 74+24\cdot 9=660,\qquad T_4=6\cdot 660+24\cdot 74=5736[/tex]
[tex]T_5=6\cdot 5736+24\cdot 660=50\,256,\qquad T_6=6\cdot 50\,256+24\cdot 5736=439\,200[/tex]
[tex]T_7=6\cdot 439\,200+24\cdot 50\,256=3\,841\,344[/tex]
Dakle, traženi broj je
[tex]9\,000\,000-3\,841\,344=5\,158\,656[/tex]

Rešenje:
Uslov za pravougaonike znači da ne postoje dve vrste i dve kolone u čija sva četiri zajednička polja stoji [tex]1[/tex]; drugim rečima, svake dve vrste imaju jedinice u najviše jednoj zajedničkoj koloni.
Za svaku vrstu posmatramo parove kolona u kojima ta vrsta ima jedinice: svaka vrsta daje [tex]\binom{3}{2}=3[/tex] takva para. Kada bi se isti par kolona pojavio kod dve različite vrste, te dve vrste i dve kolone bi obrazovale pravougaonik sa jedinicama u sva četiri ugla (zbir [tex]4[/tex]), što je zabranjeno. Prema tome, svih [tex]3n[/tex] parova su različiti parovi kolona, pa je
[tex]3n\le\binom{n}{2}=\frac{n(n-1)}{2}\Rightarrow n-1\ge 6\Rightarrow n\ge 7[/tex]
Za [tex]n=7[/tex] takva tabela postoji: numerišimo vrste i kolone od [tex]1[/tex] do [tex]7[/tex] i u vrstu [tex]i[/tex] upišimo [tex]1[/tex] u kolone [tex]i[/tex], [tex]i+1[/tex], [tex]i+3[/tex] (po modulu [tex]7[/tex]), a u ostala polja [tex]0[/tex]. Vrste sadrže jedinice u kolonama
[tex]\{1; 2; 4\},\ \{2; 3; 5\},\ \{3; 4; 6\},\ \{4; 5; 7\},\ \{5; 6; 1\},\ \{6; 7; 2\},\ \{7; 1; 3\}[/tex]
Svaka vrsta i svaka kolona sadrži tačno tri jedinice, a svaka dva od ovih skupova imaju tačno jedan zajednički element, pa nijedan pravougaonik nema jedinice u sva četiri ugla. Prema tome, najmanja moguća vrednost je [tex]n=7[/tex].

Rešenje:
Neka je [tex]\omega=-\frac{1}{2}+\frac{\sqrt{3}}{2}i[/tex]. Tada je
[tex]\omega^3=1,\qquad 1+\omega+\omega^2=0,\qquad 1+\omega=-\omega^2[/tex]
Pošto [tex]\omega^j[/tex] zavisi samo od ostatka broja [tex]j[/tex] pri deljenju sa [tex]3[/tex], imamo [tex]\sum_{0\lt j\lt n}\binom{n}{j}\omega^j=S_0+S_1\omega+S_2\omega^2[/tex]. Prema binomnoj formuli [tex]\sum_{j=0}^{n}\binom{n}{j}\omega^j=(1+\omega)^n[/tex], pa uklanjanjem sabiraka sa [tex]j=0[/tex] i [tex]j=n[/tex] dobijamo
[tex]S_0+S_1\omega+S_2\omega^2=(1+\omega)^n-1-\omega^n=(-1)^n\omega^{2n}-1-\omega^n[/tex]
Tvrđenje: [tex]S_0=S_1=S_2[/tex] ako i samo ako je [tex]S_0+S_1\omega+S_2\omega^2=0[/tex]. Ako su sva tri zbira jednaka [tex]s[/tex], leva strana je [tex]s(1+\omega+\omega^2)=0[/tex]. Obrnuto, zamena [tex]\omega^2=-1-\omega[/tex] daje [tex](S_0-S_2)+(S_1-S_2)\omega=0[/tex] sa realnim koeficijentima; pošto [tex]\omega[/tex] nije realan broj, [tex]S_1=S_2[/tex], a onda i [tex]S_0=S_2[/tex].
Dakle, potrebno je [tex](-1)^n\omega^{2n}=1+\omega^n[/tex]. Obe strane zavise samo od ostatka broja [tex]n[/tex] pri deljenju sa [tex]6[/tex]; izračunajmo ih u šest slučajeva:
[tex]n=6k:\quad (-1)^n\omega^{2n}=1,\quad 1+\omega^n=2[/tex]
[tex]n=6k+1:\quad (-1)^n\omega^{2n}=-\omega^2,\quad 1+\omega^n=1+\omega=-\omega^2[/tex]
[tex]n=6k+2:\quad (-1)^n\omega^{2n}=\omega^4=\omega,\quad 1+\omega^n=1+\omega^2=-\omega[/tex]
[tex]n=6k+3:\quad (-1)^n\omega^{2n}=-\omega^6=-1,\quad 1+\omega^n=1+\omega^3=2[/tex]
[tex]n=6k+4:\quad (-1)^n\omega^{2n}=\omega^8=\omega^2,\quad 1+\omega^n=1+\omega^4=1+\omega=-\omega^2[/tex]
[tex]n=6k+5:\quad (-1)^n\omega^{2n}=-\omega^{10}=-\omega,\quad 1+\omega^n=1+\omega^5=1+\omega^2=-\omega[/tex]
Obe strane su jednake samo za [tex]n=6k+1[/tex] i [tex]n=6k+5[/tex] (za [tex]n=6k+2[/tex] i [tex]n=6k+4[/tex] to su suprotni brojevi različiti od nule). Prema tome, uslov važi tačno za [tex]n=6k+1[/tex] i [tex]n=6k+5[/tex], [tex]k=0; 1; 2; \ldots[/tex], tj. za prirodne brojeve koji nisu deljivi ni sa [tex]2[/tex] ni sa [tex]3[/tex].
Provera za [tex]n=5[/tex]: [tex]S_1=\binom{5}{1}+\binom{5}{4}=10[/tex], [tex]S_2=\binom{5}{2}=10[/tex], [tex]S_0=\binom{5}{3}=10[/tex]; za [tex]n=4[/tex]: [tex]S_1=\binom{4}{1}=4[/tex], ali [tex]S_2=\binom{4}{2}=6[/tex].

Rešenje:
Pretpostavimo suprotno: svaki deda ima najviše [tex]13[/tex] unuka u selu. Uzmimo bilo koje dete [tex]X[/tex] i neka su [tex]A[/tex] i [tex]B[/tex] njegova dva dede. Svako drugo dete ima zajedničkog dedu sa [tex]X[/tex], pa je svako dete unuk dede [tex]A[/tex] ili dede [tex]B[/tex].
Neka su [tex]a[/tex] i [tex]b[/tex] redom brojevi unuka dede [tex]A[/tex] i dede [tex]B[/tex] u selu, a [tex]t[/tex] broj dece koja su unuci obojice. Prema principu uključenja i isključenja
[tex]a+b-t=20\Rightarrow t=a+b-20\le 13+13-20=6[/tex]
Neka je [tex]P[/tex] skup dece koja su unuci dede [tex]A[/tex], ali ne i dede [tex]B[/tex], a [tex]Q[/tex] skup dece koja su unuci dede [tex]B[/tex], ali ne i dede [tex]A[/tex]. Tada je
[tex]|P|=a-t=20-b\ge 7,\qquad |Q|=b-t=20-a\ge 7,\qquad |P|+|Q|=20-t\ge 14[/tex]
Posebno, oba skupa su neprazna. Uzmimo bilo koje [tex]Y\in P[/tex] sa dedama [tex]A[/tex] i [tex]C[/tex] (ovde je [tex]C\ne B[/tex]) i bilo koje [tex]Z\in Q[/tex] sa dedama [tex]B[/tex] i [tex]D[/tex] (ovde je [tex]D\ne A[/tex]). Deca [tex]Y[/tex] i [tex]Z[/tex] imaju zajedničkog dedu. To nije [tex]A[/tex], jer [tex]Z[/tex] nije unuk dede [tex]A[/tex], i nije [tex]B[/tex], jer [tex]Y[/tex] nije unuk dede [tex]B[/tex]. Prema tome, [tex]C=D[/tex].
Fiksirajući [tex]Z[/tex] i puštajući da [tex]Y[/tex] prolazi kroz [tex]P[/tex], vidimo da sva deca iz [tex]P[/tex] imaju istog drugog dedu [tex]D[/tex]; fiksirajući [tex]Y[/tex] i puštajući da [tex]Z[/tex] prolazi kroz [tex]Q[/tex], vidimo da i sva deca iz [tex]Q[/tex] imaju dedu [tex]D[/tex]. Dakle, deda [tex]D[/tex] ima bar [tex]|P|+|Q|\ge 14[/tex] unuka, što protivreči pretpostavci. Prema tome, postoji deda koji u selu ima bar [tex]14[/tex] unuka.