Diskretna matematika

pismeni deo ispita

januarski  ispitni rok

23.1.2006. god.

Rešenja

1. Koliko ima različitih kombinacija datuma rođenja za n ljudi, tako da su:

a. Odredimo broj kombinacija u kojima ne postoje dva čoveka među n odabrani ljudi koji su rođeni istog dana. Njih ima  (nigde u zadatku se ne kaže da neko nije rođen 29.2.). Odatle je traženi broj mogućnosti .

b. Fiksiramo jedan datum, a posle toga i dva čoveka koji su rođeni tog dana. To možemo uraditi na  načina. Među preostalih n – 2 ljudi, ne smeju da postoje dvoje sa istim datumom rođenja, i niko ne sme biti rođen fiksiranog datuma. Tu postoji  različitih mogućnosti. Dakle, ukupno ima  mogućnosti.

2.

a. Ako podskup sadrži broj n, on ne sme sadržati broj n – 1, pa je ostatak tog podskupa podskup (sa istim osobinama) skupa . Ako podskup ne sadrži broj n, onda je on podskup skupa . Odatle dobijamo vezu , ,  (i prazan skup je podskup koji zadovoljava uslove zadatka). Dakle, u pitanju su pomereni Fibonačijevi brojevi, pa je .

b. Slično kao i pod a., ako podskup sadrži n, onda on ne sme sadržati brojeve n – 1 i 1. Ostatak tog podskupa je, dakle, podskup skupa , ali u njemu mogu biti brojevi 2 i n – 2, jer oni nisu susedni na krugu. Zato ovakvih podskupova ima f(n – 3) (f iz dela a.). Ako podskup ne sadrži n, onda je on podskup skupa  i u njemu, takođe, mogu biti brojevi 1 i n – 1, pa takvih podskupova ima f(n – 1). Dakle, .

3. Očigledno je da atomi sa ovako definisanim vezama čine stablo sa n + m čvorova. To stablo ima  grana, pa primenjujući formulu za sumu stepena čvorova dobijamo da je , tj. .

4. Ako je G povezan, onda su dva čvora u istom nezavisnom skupu, ako i samo ako je dužina svakog puta između ta dva čvora parna. Ova osobina jedinstveno određuje biparticiju grafa G.

5. Problemu odgovara (neusmereni) graf sa 64 čvora koji odgovaraju poljima, a čvorovi su povezani ako između dva polja može da se odigra potez. Treba proveriti da li je takav graf Ojlerov. U slučaju skakača, čvorovi koji odogvaraju poljima a2, a7, b1, b8, g1, g8, h2, h7 imaju stepen 3, tj. neparnog su stepena, pa graf koji odgovara potezima skakača nije Ojlerov. Slično, nije ni graf koji odgovara potezima kralja (polja u uglu su povezana sa po tri druga). S’ druge strane, svako polje koje odgovara potezima topa je povezano sa 14 drugih polja, pa top može da obiđe tablu pod uslovima zadatka.