Question

Pentru a genera submulțimile unei mulțimi M={x1,x2,....xn} cu n=10 elemente se folosește metoda backtracking.Câte submulțimi cu cardinal impar se generează,submulțimi care conțin numai unul dinte elementele x1 și x3 și nu conțin elementul x2?
a) 510
b)128
c)511
d)255

Answer 1

Eliminam elementele x1, x2, x3, determinam cate submultimi cu cardinal par avem. Apoi adaugam elementele x1 sau x3.

Fara cele trei elemente eliminate avem 7 elemente in multime.

• Numar de submultimi cu 0 elemente : combinari de 7 luate cate 0 = 1
• Numar de submultimi cu 2 elemente : combinari de 7 luate cate 2 = 21
• Numar de submultimi cu 4 elemente : combinari de 7 luate cate 4 = 35
• Numar de submultimi cu 6 elemente : combinari de 7 luate cate 6 = 7

Acestea sunt submultimile cu cardinal par generate din elementele {x4, x5 ... x10}. In total sunt 64.

Adaugam elementul x1 in fiecare submultime, asta inseamna ca avem 64 de submultimi cu cardinal impar care contin x1, dar nu contin x2 sau x3.

Adaugam elementul x3 in fiecare submultime, asta inseamna ca avem 64 de submultimi cu cardinal impar care contin x3, dar nu contin x2 sau x1.

Deci in total avem 64+64=128 de astfel de multimi cautate.

Raspuns corect : b)128