Test: reguli de numărare și diagrame arborescente

Disciplina: Matematică · Clasa a X-a · Unitatea: Metode de numărare

Pentru părinți și profesori

Acest test deschide unitatea de combinatorică și verifică exact fundamentul pe care se va sprijini tot restul: capacitatea de a număra fără a enumera. Sunt evaluate patru deprinderi. Prima: diagrama arborescentă — nu ca desen decorativ, ci ca instrument care transformă o poveste („aleg întâi asta, apoi asta") într-o structură cu ramuri și frunze, unde numărul posibilităților este numărul frunzelor. A doua: regula produsului, împreună cu condiția ei de aplicare, care este locul unde se greșește cel mai des — regula cere ca numărul de variante de la fiecare etapă să nu depindă de alegerile anterioare, nu ca variantele înseși să fie aceleași. A treia: regula sumei și împărțirea corectă în cazuri, care este validă doar dacă cazurile nu se suprapun și acoperă tot. A patra: numărarea prin complement, reflexul care rezolvă în două rânduri orice enunț cu „cel puțin". Ultima parte cere și o demonstrație scrisă — cea a formulei $2^n$ pentru numărul submulțimilor — pentru că un elev care poate justifica formula nu o va mai confunda niciodată cu altceva.

• Punctaj total: 100 de puncte (90 de puncte din itemi + 10 puncte din oficiu).
• Timp recomandat: 50 de minute (o oră de curs); la itemii marcați se cer toate etapele scrise, nu doar rezultatul final.
• Cum se aplică: elevul lucrează individual, pe foaie, fără calculator (toate rezultatele se obțin prin înmulțiri și adunări simple). Un răspuns este complet doar dacă se vede raționamentul de numărare: ce se alege la fiecare etapă, câte variante are etapa și de ce se înmulțește sau se adună. Un rezultat corect fără justificare primește cel mult jumătate din punctajul subpunctului.
• Interpretare: 90–100 p = foarte bine; 75–89 p = bine; 60–74 p = satisfăcător; sub 60 p = se recomandă reluarea lecțiilor unității, cu accent pe condiția de aplicare a regulii produsului și pe verificarea faptului că împărțirea în cazuri nu lasă suprapuneri.
• Formule de reținut: regula produsului — dacă o alegere se face în $k$ etape, iar etapa $i$ are $n_i$ variante indiferent de alegerile anterioare, numărul total de posibilități este $$n_1\cdot n_2\cdot \dots \cdot n_k.$$ Cazuri particulare: $k$ poziții cu câte $n$ variante fiecare, cu repetiție, dau $n^k$ posibilități; fără repetiție, dau $n(n-1)(n-2)\cdots (n-k+1)$, adică un produs cu exact $k$ factori. Regula sumei — dacă situațiile se exclud reciproc, numerele lor se adună: $$|A\cup B|=|A|+|B|\text{caˆnd}A\cap B=\varnothing ,$$ iar dacă se suprapun, se scade partea comună: $|A\cup B|=|A|+|B|-|A\cap B|$. Numărarea prin complement: $|E|=|T|-|\overline{E}|$; contrariul lui „cel puțin unul" este „niciunul". Submulțimi: o mulțime cu $n$ elemente are exact $2^n$ submulțimi.

Notă: în barem, cuvântul „itemul" este folosit ca termen de evaluare; la clasă, în vorbirea curentă, spunem „exercițiul".

Itemi

Partea I – Diagrame arborescente și regula produsului

Itemul 1 (6 puncte)

Alege litera corespunzătoare răspunsului corect (câte 2 puncte):

a) Un meniu se compune dintr-o supă și un fel principal. Există $3$ feluri de supă și $4$ feluri principale. Numărul meniurilor diferite este: A. $7$; B. $12$; C. $34$; D. $43$.

b) Numărul submulțimilor unei mulțimi cu $5$ elemente este: A. $10$; B. $25$; C. $32$; D. $120$.

c) Un steag se compune din trei benzi verticale, colorate în trei culori diferite, alese dintr-o paletă de $5$ culori. Numărul steagurilor este: A. $10$; B. $15$; C. $60$; D. $125$.

Itemul 2 (6 puncte)

Un cod se formează alegând, în această ordine, o literă din mulțimea $\{A,B\}$ și apoi o cifră din mulțimea $\{1,2,3\}$.

a) Construiește diagrama arborescentă a acestei alegeri și scrie toate codurile obținute. (3 p)

b) Se adaugă o a treia poziție, un simbol din mulțimea $\{\ast ,\#\}$. Câte coduri se pot forma acum? Justifică folosind regula produsului. (3 p)

Itemul 3 (6 puncte)

Stabilește dacă fiecare afirmație este adevărată (A) sau falsă (F) și justifică pe scurt (câte 1,5 puncte):

a) „Dacă o alegere se face în două etape, cu $m$, respectiv $n$ variante, numărul total de posibilități este întotdeauna $m+n$."

b) „O mulțime cu $6$ elemente are $64$ de submulțimi."

c) „Regula sumei se poate aplica și atunci când cele două cazuri au elemente comune."

d) „Contrariul afirmației «cel puțin un elev a răspuns» este «niciun elev nu a răspuns»."

Itemul 4 (6 puncte)

Se formează numere de trei cifre folosind numai cifrele din mulțimea $\{0,1,2,3,4\}$, cifrele având voie să se repete.

a) Câte astfel de numere există? (3 p)

b) Câte dintre ele sunt pare? (3 p)

Partea a II-a – Regula sumei, împărțirea în cazuri și complementul

Itemul 5 (8 puncte)

Un restaurant oferă $4$ tipuri de pizza, $3$ tipuri de paste și $5$ tipuri de salată. Determină în câte moduri un client poate comanda (câte 2 puncte):

a) un singur produs;

b) o pizza și o salată;

c) exact două produse, de tipuri diferite;

d) câte un produs din fiecare tip.

Itemul 6 (7 puncte)

Se consideră numerele naturale de trei cifre.

a) Câte dintre ele au toate cifrele impare? (2 p)

b) Câte dintre ele au cel puțin o cifră pară? (3 p)

c) Câte dintre ele se termină cu $0$ sau cu $5$? (2 p)

Itemul 7 (7 puncte)

Un chestionar are trei întrebări. La prima întrebare se răspunde cu „Da" sau „Nu". Dacă răspunsul la prima întrebare a fost „Da", la a doua întrebare există $3$ variante de răspuns; dacă a fost „Nu", la a doua întrebare există doar $2$ variante. La a treia întrebare există întotdeauna $2$ variante.

a) Explică de ce nu se poate aplica direct regula produsului pe cele trei etape. (2 p)

b) Împarte problema în cazuri, construiește arborele și determină numărul total de completări posibile ale chestionarului. (5 p)

Itemul 8 (6 puncte)

Fie mulțimea $M=\{1,2,3,4,5,6\}$.

a) Câte submulțimi are $M$? (2 p)

b) Câte submulțimi ale lui $M$ îl conțin pe $1$? (2 p)

c) Câte submulțimi ale lui $M$ nu conțin niciun număr par? (2 p)

Itemul 9 (6 puncte)

Un cod de acces are $4$ caractere, fiecare caracter fiind fie o literă din mulțimea $\{A,B,C,D\}$, fie o cifră din mulțimea $\{0,1,\dots ,9\}$. Caracterele se pot repeta.

a) Câte coduri de acces există? (3 p)

b) Câte coduri încep cu o literă și se termină cu o cifră? (3 p)

Partea a III-a – Probleme practice și itemi de tip Bacalaureat

Itemul 10 (8 puncte)

(Redactare completă cerută.)

a) Demonstrează, folosind regula produsului, că o mulțime cu $n$ elemente are exact $2^n$ submulțimi. (5 p)

b) Aplică rezultatul pentru $n=7$ și determină câte submulțimi cu cel puțin un element are o mulțime cu $7$ elemente. (3 p)

Itemul 11 (8 puncte)

Într-o cantină, meniul de prânz se compune astfel: clientul alege obligatoriu un fel principal (sunt $5$ variante) și, opțional, o supă (sunt $3$ variante) și/sau un desert (sunt $4$ variante).

a) Câte meniuri diferite se pot alcătui? (4 p)

b) Câte dintre aceste meniuri conțin exact două feluri de mâncare? (4 p)

Itemul 12 (8 puncte)

Se consideră numerele naturale de patru cifre formate numai cu cifre din mulțimea $\{1,2,3,5,7\}$, cifrele având voie să se repete.

a) Câte astfel de numere există? (2 p)

b) Câte dintre ele sunt divizibile cu $5$? (3 p)

c) Câte dintre ele conțin cel puțin o cifră egală cu $7$? (3 p)

Itemul 13 (8 puncte)

(Item tip Bacalaureat.) Se consideră mulțimea $A=\{1,2,3,4,5,6,7,8\}$.

a) Determinați numărul submulțimilor mulțimii $A$. (2 p)

b) Determinați numărul submulțimilor mulțimii $A$ care conțin cel puțin un număr impar. (3 p)

c) Determinați numărul perechilor ordonate $(x,y)$ cu $x,y\in A$ și $x\ne y$. (3 p)

Barem și răspunsuri

Punctaj total: 90 p din itemi + 10 p din oficiu = 100 p.

Itemul 1. (6 p) — câte 2 puncte.

a) B. Alegerea are două etape independente: supa ($3$ variante) și felul principal ($4$ variante). Regula produsului dă $3\cdot 4=12$. Varianta A adună în loc să înmulțească — greșeala clasică: se adună doar când situațiile se exclud una pe alta, nu când se combină.

b) C. Fiecare dintre cele $5$ elemente aduce o decizie independentă („îl iau" sau „nu îl iau"), deci $2^5=32$. Varianta A confundă cu $2\cdot 5$, iar D cu $5!$.

c) C. Prima bandă: $5$ culori; a doua: $4$ (culoarea folosită nu se repetă); a treia: $3$. Deci $5\cdot 4\cdot 3=60$. Varianta D ($5^3=125$) ar fi răspunsul dacă s-ar permite repetarea culorilor.

Itemul 2. (6 p)

a) (3 p) Rădăcina arborelui are două ramuri, $A$ și $B$ (1 p); din fiecare pornesc câte trei ramuri, etichetate $1$, $2$, $3$ (1 p). Arborele are $2\cdot 3=6$ frunze, iar codurile sunt $$A1,A2,A3,B1,B2,B3$$ (1 p).

b) (3 p) Se adaugă un al treilea nivel, cu câte $2$ ramuri din fiecare frunză anterioară (1 p). Numărul de variante de la fiecare etapă nu depinde de alegerile anterioare, deci se aplică regula produsului (1 p): $$2\cdot 3\cdot 2=12\text{coduri}$$ (1 p).

Itemul 3. (6 p) — câte 1,5 puncte (0,5 p răspunsul, 1 p justificarea).

a) F. Numărul total este $m\cdot n$, nu $m+n$. Se adună doar când cele două situații se exclud reciproc (alegem fie din prima categorie, fie din a doua), nu când se combină (alegem și din prima, și din a doua). Contraexemplu: $3$ supe și $4$ feluri principale dau $12$ meniuri, nu $7$.

b) A. Fiecare element se ia sau nu se ia, independent de celelalte, deci numărul submulțimilor este $2^6=64$.

c) F. Dacă $A\cap B\ne \varnothing$, suma $|A|+|B|$ numără de două ori elementele comune. Formula corectă este $|A\cup B|=|A|+|B|-|A\cap B|$.

d) A. „Cel puțin unul" înseamnă „unul sau mai mulți"; negația acestei afirmații este exact „niciunul". Pe această echivalență se sprijină numărarea prin complement.

Itemul 4. (6 p)

a) (3 p) Numărul are trei poziții. Prima cifră nu poate fi $0$ (altfel nu ar fi un număr de trei cifre), deci are $4$ variante: $1,2,3,4$ (1,5 p). Cifra zecilor și cifra unităților au câte $5$ variante fiecare, repetiția fiind permisă (0,5 p). Prin regula produsului: $$4\cdot 5\cdot 5=100\text{numere}$$ (1 p).

b) (3 p) Numărul este par dacă ultima cifră este $0$, $2$ sau $4$ — deci $3$ variante pentru cifra unităților (1 p). Prima cifră are în continuare $4$ variante, cifra zecilor are $5$ (1 p). Rezultă $$4\cdot 5\cdot 3=60\text{numere pare}$$ (1 p). (Verificare: cele $100$ de numere se împart în $60$ pare și $40$ impare, iar $4\cdot 5\cdot 2=40$ ✓.)

Itemul 5. (8 p) — câte 2 puncte (1 p alegerea regulii, 1 p rezultatul).

a) Cele trei categorii se exclud reciproc (un singur produs înseamnă fie pizza, fie paste, fie salată), deci se aplică regula sumei: $$4+3+5=12\text{moduri}.$$

b) Două etape independente, deci regula produsului: $4\cdot 5=20$ moduri.

c) Se împarte în trei cazuri disjuncte, după perechea de tipuri aleasă, iar în interiorul fiecărui caz se înmulțește: $$\underset{\text{pizza + paste}}{\underbrace{4\cdot 3}}+\underset{\text{pizza + salata˘}}{\underbrace{4\cdot 5}}+\underset{\text{paste + salata˘}}{\underbrace{3\cdot 5}}=12+20+15=47\text{moduri}.$$ (Tiparul de bază: produs în interiorul cazului, sumă între cazuri.)

d) Trei etape independente: $4\cdot 3\cdot 5=60$ moduri.

Itemul 6. (7 p)

a) (2 p) Cifrele impare sunt $1,3,5,7,9$ — cinci variante pentru fiecare poziție, inclusiv pentru prima (niciuna nu este $0$) (1 p). Deci $5^3=125$ numere (1 p).

b) (3 p) Numărăm prin complement. Numerele de trei cifre sunt cele din intervalul $[100,999]$, în total $900$ (1 p). Contrariul afirmației „are cel puțin o cifră pară" este „are toate cifrele impare", adică exact cele $125$ de la punctul a) (1 p). Prin urmare $$900-125=775\text{numere}$$ (1 p).

c) (2 p) Cifra unităților are $2$ variante ($0$ sau $5$), cifra sutelor are $9$ (nu poate fi $0$), cifra zecilor are $10$ (1 p). Rezultă $9\cdot 10\cdot 2=180$ numere (1 p).

Itemul 7. (7 p)

a) (2 p) Regula produsului cere ca numărul de variante de la fiecare etapă să fie același, indiferent de alegerile anterioare (1 p). Aici, la a doua întrebare numărul de variante este $3$ după „Da" și $2$ după „Nu" — deci depinde de răspunsul anterior, iar regula nu se poate aplica pe tot arborele deodată (1 p).

b) (5 p) Împărțim în două cazuri disjuncte, după răspunsul la prima întrebare (1 p):

• Cazul „Da": $3$ variante la a doua întrebare, $2$ la a treia, deci $3\cdot 2=6$ completări (1,5 p).
• Cazul „Nu": $2$ variante la a doua întrebare, $2$ la a treia, deci $2\cdot 2=4$ completări (1,5 p).

Cele două cazuri se exclud reciproc și acoperă tot, deci se adună (1 p): $$6+4=10\text{completa˘ri posibile}.$$ (Arborele are exact $10$ frunze — se pot enumera și verifica una câte una.)

Itemul 8. (6 p) — câte 2 puncte.

a) Fiecare dintre cele $6$ elemente se ia sau nu se ia, deci $2^6=64$ submulțimi.

b) Elementul $1$ este fixat înăuntru, deci nu mai avem decizie asupra lui; rămân deciziile pentru celelalte $5$ elemente: $2^5=32$ submulțimi. (Verificare: submulțimile care îl conțin pe $1$ și cele care nu îl conțin sunt tot atâtea, iar $32+32=64$ ✓.)

c) A nu conține niciun număr par înseamnă a fi submulțime a mulțimii numerelor impare $\{1,3,5\}$, care are $2^3=8$ submulțimi.

Itemul 9. (6 p)

a) (3 p) Alfabetul codului are $4+10=14$ simboluri (1 p). Fiecare dintre cele $4$ poziții se completează independent, cu oricare dintre cele $14$ simboluri (1 p): $$14^4=38416\text{coduri}$$ (1 p).

b) (3 p) Ocupăm întâi pozițiile restricționate. Prima poziție: $4$ variante (doar litere); ultima poziție: $10$ variante (doar cifre) (1,5 p). Pozițiile a doua și a treia rămân libere, cu câte $14$ variante (0,5 p). Rezultă $$4\cdot 14\cdot 14\cdot 10=7840\text{coduri}$$ (1 p).

Itemul 10. (8 p) — redactare completă.

a) (5 p) Fie $M=\{x_1,x_2,\dots ,x_n\}$ o mulțime cu $n$ elemente. A construi o submulțime a lui $M$ înseamnă a lua, pentru fiecare element în parte, o decizie: îl includ sau nu îl includ (1,5 p).

Construcția se face deci în $n$ etape: la etapa $i$ hotărâm soarta elementului $x_i$, iar la fiecare etapă avem exact $2$ variante (1 p). Numărul de variante de la o etapă nu depinde în niciun fel de deciziile luate anterior — condiția de aplicare a regulii produsului este îndeplinită (1 p). Prin urmare numărul de submulțimi este $$\underset{n\text{factori}}{\underbrace{2\cdot 2\cdot \dots \cdot 2}}=2^n$$ (1 p).

Corespondența este bijectivă: fiecare șir de $n$ decizii dă o singură submulțime, iar două șiruri diferite dau submulțimi diferite; șirul „nu includ nimic" dă mulțimea vidă, iar șirul „includ tot" dă chiar $M$ — ambele sunt submulțimi și au fost numărate (0,5 p). $■$

b) (3 p) Pentru $n=7$ obținem $2^7=128$ submulțimi (1,5 p). Dintre acestea, una singură nu are niciun element (mulțimea vidă), deci numărul submulțimilor cu cel puțin un element este $$128-1=127$$ (1,5 p). (Este numărare prin complement: contrariul lui „cel puțin un element" este „niciun element".)

Itemul 11. (8 p)

a) (4 p) Trucul stă în tratarea alegerilor opționale: „fără supă" este și ea o variantă, deci supa are $3+1=4$ variante, iar desertul $4+1=5$ variante (2 p). Felul principal este obligatoriu și are $5$ variante (0,5 p). Cele trei alegeri sunt independente, deci $$5\cdot 4\cdot 5=100\text{meniuri}$$ (1,5 p).

b) (4 p) Felul principal este întotdeauna prezent, deci „exact două feluri" înseamnă că exact unul dintre celelalte două este ales. Împărțim în două cazuri disjuncte (1 p):

• fel principal + supă, fără desert: $5\cdot 3=15$ meniuri (1,5 p);
• fel principal + desert, fără supă: $5\cdot 4=20$ meniuri (1 p).

Prin regula sumei, $15+20=35$ de meniuri (0,5 p). (Verificare a împărțirii totale: $5$ meniuri cu un singur fel, $35$ cu două feluri și $5\cdot 3\cdot 4=60$ cu trei feluri; într-adevăr $5+35+60=100$ ✓.)

Itemul 12. (8 p)

a) (2 p) Fiecare dintre cele $4$ poziții se completează cu oricare dintre cele $5$ cifre disponibile, niciuna nefiind $0$, deci prima poziție nu are restricție suplimentară (1 p): $$5^4=625\text{numere}$$ (1 p).

b) (3 p) Un număr este divizibil cu $5$ dacă se termină în $0$ sau în $5$; cifra $0$ nu este disponibilă, deci ultima cifră trebuie să fie $5$ — o singură variantă (1,5 p). Celelalte trei poziții rămân libere (0,5 p): $$5^3\cdot 1=125\text{numere}$$ (1 p).

c) (3 p) Numărăm prin complement (1 p). Numerele care nu conțin cifra $7$ se formează doar cu cifrele $\{1,2,3,5\}$, deci sunt $4^4=256$ (1 p). Prin urmare cele care conțin cel puțin un $7$ sunt $$625-256=369$$ (1 p). (Numărarea directă pe cazuri — exact un $7$, exact doi de $7$ și așa mai departe — dă același rezultat, dar cere patru calcule în loc de unul.)

Itemul 13. (8 p)

a) (2 p) Mulțimea $A$ are $8$ elemente, deci numărul submulțimilor ei este $$2^8=256$$ (2 p).

b) (3 p) Numărăm prin complement (1 p). Contrariul afirmației „conține cel puțin un număr impar" este „nu conține niciun număr impar", adică submulțimea este inclusă în mulțimea numerelor pare $\{2,4,6,8\}$. Aceasta are $2^4=16$ submulțimi (1 p). Rezultă $$256-16=240\text{submulțimi}$$ (1 p).

c) (3 p) Perechea este ordonată, deci alegerea se face în două etape: mai întâi $x$, apoi $y$ (1 p). Pentru $x$ avem $8$ variante; după fixarea lui $x$, pentru $y$ rămân $7$ variante, condiția $y\ne x$ eliminând exact o valoare — și eliminând-o oricare ar fi $x$, deci regula produsului se aplică (1 p): $$8\cdot 7=56\text{perechi}$$ (1 p). (Verificare: perechile ordonate cu $x,y\in A$ sunt în total $8^2=64$, dintre care $8$ au $x=y$; într-adevăr $64-8=56$ ✓.)