PROBLEME DE NUMRARE

Sergiu Prisacariu, Colegiul Naional Iai Gabriel Popa, Colegiul Naional Iai

Reguli de numrare

- Dac mulimile A i B sunt disjuncte, atunci card (A B) = card A + card B. - Card (A B) = card A + card B card (A B). - Card (A B C) = card A + card B + card C card (A B) card (B C) card (C A) +

card (A B C). - Regula produsului: card AB = card A card B. - Pentru a numra elementele unei mulimi, cutm s-o nlocuim cu o alt mulime, avnd

acelai numr de elemente i ale crei elemente pot fi mai uor numrate.

Probleme propuse

1. a) Stabilii cte numere naturale mai mici ca 2014 sunt divizibile sau cu 2 sau cu 3 sau cu 5. b) Stabilii cte numere naturale mai mici ca 2014 sunt relativ prime cu 30.

Soluie. a) Folosim principiul includerii i excluderii. Avem: Card(M2) = 1007, Card(M3) = 672, Card(M5) = 403, Card(M2 M3) = Card(M6) = 336, Card(M3 M5) = Card(M15) = 135, Card(M5 M2) = Card(M10) = 202, Card(M2 M3 M5) = Card(M30) = 68, deci card(M2 M3 M5) = = 1007 + 672 + 403 336 135 202 + 68 = 1477. b) Evident, numrul cerut este egal cu 2014 1477 = 537.

2. Determinai cardinalul mulimii 2

2

3, 1,2,...,50

nM x x n

n n

.

Soluie. Dac toate fraciile de tipul 2

2

3

nn n

ar fi distincte, M ar avea 50 de elemente; acest fapt ne se

ntmpl ns. Condiia xn = xm conduce la 2 2

2 2

3 3n mn n m m

, de unde (n 3) (m 3) = 12, prin

urmare au loc egalitile x4 = x15, x5 = x9, x6 = x7. Astfel, cardM = 50 3 = 47. 3. Calculai numrul maxim de elemente care pot fi alese din mulimea 1, 2, 3, , 2014, astfel nct suma oricror dou elemente alese s nu fie divizibil cu 3.

Soluie. Nu putem alege mai mult de un multiplu de trei. De asemenea, nu putem alege n acelai timp un numr de forma M3 + 1 i unul de forma M3 + 2, deoarece suma lor se va divide cu 3. Cum Card(M3 + 1) = 672, Card(M3 + 2) = 671 i dorim s alegem ct mai multe numere, vom lua un multiplu de 3 i toate numerele de forma M3 + 1, adic 672 + 1 = 673 numere. 4. Cte numere de n cifre, n 2, se pot forma cu cifrele 1 i 2 (fiecare cifr apare mcar o dat)?

Soluie. Folosind cifrele 1 i 2, putem forma 2n numere de n cifre. Dintre acestea, 2 numere nu convin, fiind formate doar din cifre de 1 sau doar din cifre de 2. Rmne c exist an = 2n 2 numere cu proprietile cerute. 5. Cte numere de n cifre, n 3, se pot forma cu cifrele 1, 2 i 3 (fiecare cifr apare mcar o dat)?

Soluie. Folosind cifrele 1, 2 i 3, putem forma 3n numere de n cifre. Dintre acestea, 3 numere sunt formate doar din cifre de 1, de 2 sau de 3. Apoi, an conin doar cifre de 1 sau 2, an conin doar cifre de 1 sau 3, iar an conin doar cifre de 2 sau 3. Rmne c exist bn = 3n 3(2n 2) 3 = 3n 3 2n + 3 numere cu proprietile cerute. 6. n cte moduri poate fi pavat un dreptunghi 2 10 cu plci de dimensiuni 1 2 ?

Soluie. Notm cu an numrul pavrilor dreptunghiului 2n cu plci de dimensiuni 1 2 . Observm c 1 1,a 2 2,a iar 1 2 n n na a a . Din aproape n aproape, obinem c 10 89a . 7. Se scriu n ordine cresctoare toate numerele nenule din baza 10 n a cror scriere nu apar alte cifre afar de 0, 1, 2 i 3. Care este cel de-al 2014-lea numr scris?

Soluie. De fapt, se scriu toate numerele naturale n baza 4, n ordine cresctoare. ntrebarea este ce form are numrul 2014 n baza 4. Avem c (10) (4)2014 133132 .

8. Un elev are 10 bile numerotate cu numerele 1, 2, , 10. El trebuie s le pun n trei urne identice astfel nct n nici o urn s nu fie dou bile numerotate cu numere consecutive. n cte moduri poate face acest lucru?

Soluie. Prima bil poate fi aezat n oricare dintre cele trei urne, iar fiecare dintre urmtoarele bile poate fi aezat n oricare dintre cele dou urne n care nu se afl bila anterioar ei. Obinem 3 29 modaliti de aezare a bilelor. 9. Se numete matrice de tip m n un tablou cu m linii i n coloane, ale crui celule sunt completate cu numere reale. Notm cu M mulimea matricelor de tip 4 4, completate cu elemente din

mulimea 1, 0,1 . a) Care este cardinalul mulimii M ? b) Cte dintre matricele din M au numai 0 pe diagonala principal? Dar mcar un 0? c) Cte dintre matricele din M sunt simetrice fa de diagonala principal?

Soluie. a) Avem de completat 16 poziii cu trei numere. Obinem c M conine 316 matrice.

b) Avem de completat, cu trei numere, 12 poziii; cele 4 de pe diagonala principal se completeaz forat, cu zerouri. Rezult c M conine 312 matrice cu 0 pe diagonala principal. n ceea ce privete a doua ntrebare, M conine 24 312 matrice care nu conin zerouri pe diagonala principal, deci 316 24 312 = 65 312 matrice conin mcar un 0 pe diagonala principal. c) Avem de completat, cu trei numere, 10 poziii: cele 4 de pe diagonala principal, precum i cele 6 de deasupra acesteia. Poziiile de sub diagonala principal se completeaz forat, datorit simetriei. Obinem c M conine 310 matrice simetrice fa de diagonala principal. 10. Determinai numrul matricelor de tip 3 3, avnd ca elemente numerele 1 sau 1, n care produsul elementelor de pe fiecare linie i de pe fiecare coloan este 1.

Soluie. Avem libertate de completare doar ntr-un ptrat 2 2 ; restul de cinci poziii din matrice se completeaz forat, astfel nct produsul elementelor de pe fiecare linie i de pe fiecare coloan s fie

1. n concluzie, exist 24 = 16 matrice cu proprietatea dorit. 11. Artai c o mulime cu n elemente are 2n submulimi.

Soluie. Fie 1 2, ,..., nA a a a mulime cu n elemente. Asociem fiecrei submulimi B a lui A o secven 1 2, ,..., nx x x , format numai din 0 i 1, astfel: 1 i ix a B i 0 i ix a B . Se observ uor c numrul submulimilor lui A coincide cu numrul secvenelor de n caractere, formate numai din 0 i 1. Cum numrul acestor secvene este 2n , nseamn c A are 2n submulimi. 12. Determinai numrul perechilor de mulimi ,A B care ndeplinesc simultan condiiile: (i) 1,2,3,..., 2014A B ; (ii) 1,2,3,...,1007A B ; (iii) \A B .

Soluie. Colorm elementele lui A B cu patru culori: cu rou elementele lui A B , cu albastru elementele lui \A B , cu verde elementele lui \B A i cu galben elementele rmase. Numrm mai nti perechile ,A B care ndeplinesc ipotezele (i) i (ii): numerele 1,2,3,...,1007 pot fi colorate cu oricare dintre cele patru culori, n timp ce numelele 1008,1009,..., 2014 nu pot fi colorate cu rou; obinem deci 41007 31007 astfel de mulimi. Dintre acestea, 31007 21007 nu ndeplinesc ipoteza (iii), ntruct nu mai putem folosi culoarea albastr. Rmne c numrul perechilor cutate este egal cu 31007 (41007 21007).

Tem 1. Dintr-o clas de 30 elevi, la olimpiada de limba romn au participat 15 elevi, la matematic au participat 12 elevi i 5 elevi au participat la ambele. Ci elevi nu au participat la nicio olimpiad?

Soluie. Folosind notaii sugestive, avem: Card(R M) = 15 + 12 5 = 22. Rezult c 30 22 = 8 elevi nu au participat la nicio olimpiad.

2. Fie mulimile A = 3n 2 n N, B = 1003 2m m N i C = 6p + 1 p 0,167 .

Artai c A B = C.

Soluie. Dac x A B, atunci x = 3n 2 = 1003 2m, prin urmare n = 2k + 1 i m = 501 3k. Deducem c x = 6p + 1 i se arat uor c p 0,167 , aadar A B C . Incluziunea invers este imediat.

3. Determinai cardinalul mulimii

, , 456 5

nM x x n n

n n.

Soluie. Procednd ca n soluia problemei 2 din primul set, obinem c mulimea M are cardinalul 91 8 = 83. 4. Determinai numrul maxim de elemente dintr-o mulime A inclus n 1, 2, ... , 2013 astfel nct, oricum am lua dou numere din A, suma lor s nu fie divizibil cu diferena lor.

Soluie. Nu exit n A dou numere consecutive, pentru c diferena lor, 1, va divide suma lor. Nu exist n A nici dou numere a cror diferen s fie 2, deoarece n acest caz, numerele vor avea aceeai paritate, deci suma lor va fi par i se va divide cu diferena. Rezult c A are cel mult 671 de elemente, ntruct dac vom considera mai multe, cel puin dou vor aparine unei aceleiai clase ale partiiei

1, 2, 3, ... , 2010 1,2,3 4,5,6 ... 2011,2012,2013 , iar diferena dintre aceste dou numere va fi 1 sau 2. Exist mulimi A cu exact 671 de elemente, de exemplu 1, 4, 7, ... , 2011 :A diferena oricror dou elemente ale acestei mulimi este multiplu de 3, pe cnd suma acestor elemente este 3 2.M 5. Cte numere de n cifre, n 4, se pot forma cu cifrele 1, 2, 3 i 4 ( fiecare cifr apare mcar o dat)?

Soluie. Procednd ca n soluia problemei 6 din primul set, obinem c numrul cutat este egal cu cn = 4n 4 3n + 6 2n 4. 6. Pe cte drumuri poate ajunge un rege care se afl pe tabla de ah din cmpul 1A n cmpul 8,A efectund exact 7 mutri?

Soluie. Atam fiecrui cmp al tablei de ah cte un numr care arat cte drumuri care pleac din

1A ajung pn n cmpul respectiv, n numr minim posibil de mutri. Urmrind cum se completeaz tabla cu numere, observm c numrul ataat unui cmp este suma numerelor din cele (cel mult) trei cmpuri aflate imediat sub el. Cmpului 8A i se asociaz numrul 127. 7. Determinai numrul matricelor de tip 3 3, avnd ca elemente numerele 1 sau 1, n care produsul tuturor elementelor matricei este 1.

Soluie. Avem libertate de completare n 15 dintre poziiile matricei; a 16-a poziie se completeaz forat, astfel nct produsul elementelor matricei s fie 1. Astfel, exist 215 matrice cu proprietatea dorit. 8. Stabilii cte matrice n n , completate cu numere ntregi, au proprietatea c produsul elementelor de pe fiecare linie i de pe fiecare coloan este 5 sau 5 .

Soluie. Fiecare linie i fiecare coloan trebuie s conin cte un unic numr de modul 5; exist n! modaliti de aezare a acestor numere. Restul poziiilor vor fi completate cu numere de module egal cu 1. Apoi, pentru fiecare poziie putem alege, la ntmplare, unul dintre semnele + sau ; acest lucru

poate fi realizat n 2

2n moduri. n concluzie, exist 2

2 !n n matrice ca n enunul problemei.

9. Pe o tabl de ah 8 8 se aeaz 8 turnuri astfel nct niciunul s nu atace vreunul dintre celelalte. a) Artai c un astfel de aranjament este posibil. Cte asemenea aranjamente exist? b) Pentru un astfel de aranjament de turnuri pe tabl, artai c n orice ptrat 5 5 de pe tabl exist cel puin dou turnuri.

Soluie. a) Pe fiecare linie i pe fiecare coloan trebuie s existe exact un turn. Exist 8! modaliti de aezare a turnurilor astfel nct acestea s nu se atace reciproc. b) Rmn n afara ptratului 5 5, trei linii pe care sunt trei turnuri. Rmn n afara ptratului trei coloane pe care sunt cel mult trei turnuri. n afara ptratului sunt cel mult 6 turnuri (deci n ptratul 5 5 sunt cel puin dou turnuri). 10. Determinai cardinalul mulimii A, n cazul n care card (AA) = card P (A).

Soluie. Condiia din enun revine la n2 = 2n, deci n 2;4. 11. Dac 1 21 2 ... k

aa akn p p p , unde p1, p2,,pk sunt numere prime iar a1, a2,,ak

, demonstrai c numrul divizorilor naturali ai lui n este 1 21 1 ... 1 ka a a .

Soluie. Dac x este divizor al lui n, atunci el are forma 1 21 2 ... kii ikx p p p , cu i1 0, 1, , a1, ,

ik 0, 1, , ak. Folosind regula produsului, urmeaz concluzia problemei.