Diskretna matematika

pismeni deo ispita

januarski  ispitni rok

23.1.2006. god.

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

a. bar dva čoveka rođena istog dana;

b. tačno dva čoveka rođena istog dana.

2. Neka je .

a. Odrediti broj f(n) podskupova skupa  koji ne sadrže par uzastopnih brojeva.

b. Ako su brojevi  poređani na krugu, odrediti broj g(n) podskupova skupa  koji ne sadrže dva broja koji su na krugu jedan do drugog.

3. Zasićeni hidrokarbonat je molekul  u kome svaki atom ugljenika ima 4 veze, svaki atom vodonika ima jednu vezu i ne postoje veze koje čine cikl. Dokazati da takav atom može da postoji samo ako je .

4. Dokazati da ako je bipartitan graf G povezan, onda ima jedinstvenu biparticiju.

5. Da li skakač u šahu može da obiđe šahovsku tablu, tako da svaki mogući potez bude odigran tačno jednom (smatra se da je potez između dva polja odigran ako se figura pomeri sa jednog na drugo u bilo kom smeru)? Da li isto važi i za kralja i topa?

Rezultati:                    četvrtak, 26.1.2006. god. u 12.00