Diskretna matematika i teorija grafova - teški zadaci sa rešenjima

Rešenje:
Za svako [tex]n\ge 0[/tex] važi [tex]\binom{n}{3}=\frac{n(n-1)(n-2)}{6}[/tex] (za [tex]n=0; 1; 2[/tex] obe strane su jednake [tex]0[/tex]), pa je
[tex]f(n)=q(n)\,(-1)^n,\qquad q(n)=\frac{n(n-1)(n-2)}{6}[/tex]
gde je [tex]q[/tex] polinom stepena [tex]3[/tex]. Opšte rešenje rekurentne relacije sa karakterističnim polinomom [tex](x+1)^4[/tex] je [tex](C_1+C_2n+C_3n^2+C_4n^3)(-1)^n[/tex], jer je [tex]-1[/tex] koren višestrukosti [tex]4[/tex]. Prema tome, [tex]f[/tex] zadovoljava relaciju reda [tex]4[/tex] sa karakterističnim polinomom
[tex](x+1)^4=x^4+4x^3+6x^2+4x+1[/tex]
tj. relaciju
[tex]f(n)=-4f(n-1)-6f(n-2)-4f(n-3)-f(n-4)[/tex]
Takva relacija reda [tex]k\le 3[/tex] ne postoji: za [tex]n=3[/tex] njena desna strana je linearna kombinacija nekih od vrednosti [tex]f(0)[/tex], [tex]f(1)[/tex], [tex]f(2)[/tex], koje su jednake [tex]0[/tex], a [tex]f(3)=-1\ne 0[/tex]. Dakle, najmanji mogući red je [tex]4[/tex]. Provera sa [tex]f(3)=-1[/tex], [tex]f(4)=4[/tex], [tex]f(5)=-10[/tex]:
[tex]f(4)=-4f(3)=-4\cdot (-1)=4; \qquad f(5)=-4f(4)-6f(3)=-16+6=-10[/tex]

Rešenje:
Podelimo rekurentnu relaciju sa [tex](n+1)![/tex] i uvedimo [tex]b_n=\frac{a_n}{n!}[/tex]. Tada je [tex]b_1=0[/tex] i
[tex]b_{n+1}-b_n=\frac{(-1)^{n+1}}{(n+1)!},\quad n\ge 1[/tex]
Sabiranjem ovih jednakosti za indekse od [tex]1[/tex] do [tex]n-1[/tex] (leva strana je teleskopska suma) dobijamo
[tex]b_n=b_1+\sum_{k=2}^{n}\frac{(-1)^k}{k!}=\sum_{k=0}^{n}\frac{(-1)^k}{k!}[/tex]
jer članovi za [tex]k=0[/tex] i [tex]k=1[/tex] daju [tex]1-1=0=b_1[/tex] (za [tex]n=1[/tex] suma od [tex]k=2[/tex] je prazna). Množenjem sa [tex]n![/tex] dobijamo [tex]a_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}[/tex].
Provera: iz rekurentne relacije [tex]a_2=1[/tex], [tex]a_3=2[/tex], [tex]a_4=9[/tex], a po formuli
[tex]2!\left(1-1+\frac{1}{2}\right)=1; \quad 3!\left(\frac{1}{2}-\frac{1}{6}\right)=2; \quad 4!\left(\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=9[/tex]

Rešenje:
Označimo Hamingovo rastojanje sa [tex]d[/tex]. Vektori [tex]\alpha[/tex] i [tex]\beta[/tex] razlikuju se na pozicijama [tex]1[/tex], [tex]3[/tex], [tex]6[/tex], [tex]7[/tex], a poklapaju se na pozicijama [tex]2[/tex], [tex]4[/tex], [tex]5[/tex], tj. [tex]d(\alpha,\beta)=4[/tex].
Na poziciji na kojoj se [tex]\alpha[/tex] i [tex]\beta[/tex] poklapaju, [tex]\gamma[/tex] dodaje isti broj ([tex]0[/tex] ili [tex]1[/tex]) i rastojanju [tex]d(\gamma,\alpha)[/tex] i rastojanju [tex]d(\gamma,\beta)[/tex]. Zato te [tex]3[/tex] pozicije ne utiču na jednakost i na njima je [tex]\gamma[/tex] proizvoljan: [tex]2^3=8[/tex] mogućnosti.
Na svakoj od [tex]4[/tex] pozicije na kojima se razlikuju, [tex]\gamma[/tex] se poklapa sa tačno jednim od vektora [tex]\alpha[/tex] i [tex]\beta[/tex], pa dodaje [tex]1[/tex] tačno jednom od dva rastojanja. Prema tome, [tex]d(\gamma,\alpha)=d(\gamma,\beta)[/tex] ako i samo ako se [tex]\gamma[/tex] poklapa sa [tex]\alpha[/tex] na tačno [tex]2[/tex] od te [tex]4[/tex] pozicije (a sa [tex]\beta[/tex] na preostale [tex]2[/tex]): [tex]\binom{4}{2}=6[/tex] mogućnosti.
Prema pravilu proizvoda, broj traženih vektora je
[tex]\binom{4}{2}\cdot 2^3=6\cdot 8=48[/tex]

Rešenje:
Neka je [tex]G[/tex] takav graf i pretpostavimo da neki čvor [tex]v[/tex] ima stepen bar [tex]3[/tex] u [tex]G[/tex]; neka su [tex]a,b,c[/tex] tri njegova suseda. Ako su dva od njih susedna u [tex]G[/tex], oni zajedno sa [tex]v[/tex] obrazuju trougao u [tex]G[/tex]; u suprotnom [tex]a,b,c[/tex] obrazuju trougao u [tex]\overline{G}[/tex]. Dakle, svaki stepen u [tex]G[/tex] je najviše [tex]2[/tex].
Uslov je simetričan u odnosu na [tex]G[/tex] i [tex]\overline{G}[/tex], pa je i svaki stepen u [tex]\overline{G}[/tex] najviše [tex]2[/tex]. Svaki čvor ima [tex]4[/tex] moguća suseda, pa je
[tex]d_G(v)=4-d_{\overline{G}}(v)\ge 4-2=2[/tex]
Dakle, svaki stepen u [tex]G[/tex] jednak je [tex]2[/tex], tj. [tex]G[/tex] je unija disjunktnih ciklusa, svakog dužine bar [tex]3[/tex], sa ukupno [tex]5[/tex] čvorova. Kako [tex]5[/tex] nije zbir dva ili više brojeva [tex]\ge 3[/tex], graf [tex]G[/tex] je jedan ciklus dužine [tex]5[/tex].
Obrnuto, ciklus dužine [tex]5[/tex] ne sadrži trougao, a njegov komplement je ponovo ciklus dužine [tex]5[/tex] (svaki čvor se spaja sa dva čvora koji mu nisu susedi, pa se dobija pentagram), tako da ni on ne sadrži trougao.
Ostaje da prebrojimo cikluse dužine [tex]5[/tex] na [tex]5[/tex] označenih čvorova. Svaki od [tex]5![/tex] rasporeda čvorova daje ciklus, pri čemu se svaki ciklus dobija [tex]5\cdot 2[/tex] puta ([tex]5[/tex] početnih čvorova i [tex]2[/tex] smera):
[tex]\frac{5!}{5\cdot 2}=\frac{120}{10}=12[/tex]

Rešenje:
Neka je [tex]n=|V|[/tex]. Najpre pokažimo da je [tex]|E|\lt 3n[/tex]. Za [tex]n\le 2[/tex] to je jasno, jer je [tex]|E|\le 1[/tex]. Neka je [tex]n\ge 3[/tex]. Dodavanje grane između dve komponente ravanskog crteža čuva planarnost i samo povećava [tex]|E|[/tex], pa možemo smatrati da je [tex]G[/tex] povezan. Tada obilazak granice svake oblasti ima dužinu bar [tex]3[/tex], a svaka grana se u tim obilascima broji najviše dva puta. Zajedno sa Ojlerovom formulom [tex]n-|E|+F=2[/tex], gde je [tex]F[/tex] broj oblasti, to daje
[tex]3F\le 2|E|\ \Rightarrow\ 3(2-n+|E|)\le 2|E|\ \Rightarrow\ |E|\le 3n-6\lt 3n[/tex]
Prema lemi o rukovanju
[tex]\sum_{v\in V}d(v)=2|E|\lt 6n[/tex]
Neka je [tex]D=\frac{600}{100-p}\gt 0[/tex] i neka je [tex]q[/tex] broj čvorova za koje je [tex]d(v)\ge D[/tex]. Svaki od njih doprinosi zbiru stepena bar [tex]D[/tex], pa je
[tex]qD\le\sum_{v\in V}d(v)\lt 6n\ \Rightarrow\ q\lt\frac{6n}{D}=\frac{6n(100-p)}{600}=\frac{(100-p)n}{100}[/tex]
Prema tome, broj čvorova stepena manjeg od [tex]D[/tex] je
[tex]n-q\gt n-\frac{(100-p)n}{100}=\frac{pn}{100}[/tex]
tj. više od [tex]p\%[/tex] svih čvorova. Time je tvrđenje dokazano.

Rešenje:
Niko se ne rukuje sa samim sobom ni sa svojim supružnikom, pa je svaki odgovor jedan od brojeva od [tex]0[/tex] do [tex]8[/tex]. Devet odgovora je različito, dakle to su tačno
[tex]0,1,2,\ldots,8[/tex]
Osobu koja je odgovorila [tex]j[/tex] nazovimo „osoba [tex]j[/tex]“. Osoba [tex]8[/tex] rukovala se sa svima osim sa svojim supružnikom. Osoba [tex]0[/tex] nije se rukovala ni sa kim, pa ni sa osobom [tex]8[/tex], zato je osoba [tex]0[/tex] supružnik osobe [tex]8[/tex]. Obe su bile pitane, pa nijedna od njih nije gospođa Ivanova; a osoba [tex]8[/tex] nije gospodin Ivanov, jer njegova supruga, gospođa Ivanova, nije bila pitana. Dakle, osobe [tex]8[/tex] i [tex]0[/tex] čine jedan od gostujućih parova.
Uklonimo ovaj par. Svaka od preostalih osoba rukovala se sa osobom [tex]8[/tex], a nije se rukovala sa osobom [tex]0[/tex], pa se svaki od preostalih brojeva smanjuje tačno za [tex]1[/tex]. Dobijamo istu situaciju sa [tex]3[/tex] gostujuća para: sedam pitanih osoba sada ima različite brojeve [tex]0,1,\ldots,6[/tex].
Ponavljajući rasuđivanje, dobijamo da osobe [tex]7[/tex] i [tex]1[/tex], zatim [tex]6[/tex] i [tex]2[/tex], zatim [tex]5[/tex] i [tex]3[/tex] čine gostujuće parove, a poslednja pitana osoba, osoba [tex]4[/tex], je gospodin Ivanov. U svakom koraku osoba sa najvećim brojem rukovala se sa svim prisutnima osim sa svojim supružnikom, posebno sa gospođom Ivanovom, dok se osoba sa brojem [tex]0[/tex] nije rukovala sa njom. Gospođa Ivanova se nije rukovala ni sa svojim mužem. Prema tome, rukovala se tačno sa osobama [tex]8[/tex], [tex]7[/tex], [tex]6[/tex] i [tex]5[/tex], tj. sa [tex]4[/tex] osobe.