1. Consideram urmatoarele transformari asupra unui graf orientat: 
   - partitionam varfurile in componente tare conexe ale grafului
   - inlaturam toate arcele care leaga doua varfuri din aceeasi 
componenta tare conexa.
   Demonstrati ca graful obtinut este aciclic.


2. Demonstrati ca un nodurile unui graf pot fi colorate cu doua culori, 
astfel incat oricare doua varfuri adiacente au culori diferite, daca si 
numai daca toate ciclurile sunt de lungime para.


3. In cate moduri pot fi puse 4 bile in 4 urne daca: 
   (a) bilele sunt distincte si urnele sunt distincte
   (b) bilele sunt distincte, iar urnele sunt identice.
   (c) urnele sunt distincte, dar bilele sunt identice.
   (d) bilele sunt identice si urnele sunt identice.


4. Un profesor vrea sa imparta cei 12 elevi dintr-o clasa in 4 grupuri 
de cate 3 persoane. Cate moduri diferite de a forma aceste grupuri 
exista ?


5. In conducerea unei companii sunt sase femei si noua barbati. In cate 
moduri se poate forma un comitet de 5 persoane, dintre care cel putin o 
femeie ? 


6. Mai jos este prezentata o lista de proprietati pe care le poate avea 
un grup de persoane. Pentru fiecare dintre aceste proprietati, dati 
numarul minim de persoane pe care trebuie sa-l aiba grupul astfel incat 
proprietatea sa fie cu siguranta indeplinita, sau indicati inexistenta 
unui asemenea numar (altfel spus, grupul poate sa nu aiba acea 
proprietate, indiferent de numarul de persoane). Considerati ca fiecare an are 
365 de zile (se ignora anii bisecti).
   (a) Cel putin 2 persoane s-au nascut in aceeasi zi a anului.
   (b) Cel putin doua persoane s-au nascut pe 1 ianuarie.
   (c) Cel putin 3 persoane s-au nascut in aceeasi zi a saptamanii.
   (d) Cel putin 4 persoane s-au nascut in aceeasi luna.
   (e) Cel putin 2 persoane s-au nascut la distanta de exact o 
saptamana.
   (f) Cel putin 9 persoane s-au nascut intr-un week-end sau cel putin 
11 persoane s-au nascut in timpul saptamanii.
   (g) Cel putin 2 persoane s-au nascut in aceeasi zi a anului sau 2 
persoane s-au nascut la distanta de exact o saptamana.


7. Fie un graf neorientat G = (V, E). Consideram Gc = (V, Ec) graful 
complementar lui G: altfel spus, Gc contine exact acele muchii care nu se 
afla in G.
   Demonstrati ca daca graful G nu este conex, atunci Gc este.

  
8. 11 oameni de stiinta lucreaza la un proiect secret. Ei doresc sa 
incuie documentele legate de proiect intr-un seif astfel incat acesa sa 
poata fi deschis daca si numai daca sase sau mai multi oameni de stiinta 
sunt prezenti.
   (a) Care este numarul cel mai mic de incuietori cu care se poate 
realiza acest lucru ?
   (b) Care este cel mai mic numar de chei pe care trebuie sa-l care 
fiecare om de stiinta ?


9. In cate moduri pot fi ordonate cele 26 de litere ale alfabetului 
englez astfel incat oricare doua vocale nu sunt adiancente, iar ultima 
litera nu este o vocala ?


10. In cate moduri pot fi ordonate cele 26 de litere ale alfabetului 
englez astfel incat intre oricare doua vocale exista cel putin doua 
consoane, iar ultimele doua litere nu sunt vocale ?




--------------------------------------------------------------------------------

3. (a) 256
   (b) 15
   (c) 35
   (d) 5

 
4. 15400

5. 2877

6. (a) 366
   (b) NU
   (c) 15
   (d) 37
   (e) NU
   (f) 19
   (g) 183 / 184 (primul raspuns e valabil daca se considera, de 
exemplu, ca o persoana nascuta pe 31 decembrie si o persoana nascuta pe 6 
ianuarie sunt la o saptamana una de cealalta).

        11
8. (a) C    
        6
        10
   (b) C
        5


9. (21!)^2 / 16!

10. 16!21! / 11!


