Cardinale Finite Si Transcendente. Probleme de Numarare

LUCRARE DE DISERTAȚIE

TEMA:

CARDINALE FINITE ȘI TRANSCENDENTE. PROBLEME DE NUMĂRARE

INTRODUCERE

Lucrarea de față are la bază o idee mai veche a autorului de a aduna într-un tot materialele pe această temă, susținute în cadrul cercurilor de matematică efectuate pe parcursul ultimilor ani cu elevii dornici de performanță, atât la clasele de gimnaziu cât și la cele de liceu. Ordinea în care temele au fost abordate s-a dorit a fi una care să poarte cititorul de la unele noțiuni teoretice de bază care privesc numerele cardinale și aplicațiile acestora în teoria numerelor, relativ simple ca mod de abordare, la cele mai puțin familiare care privesc problemele de numărare și principiile care stau la baza lor.

Bogata experiență acumulată pe parcursul anilor în care am pregătit și elevi de gimnaziu m-a făcut să înțeleg că un copil de 11-12 ani, ghidat cu grijă, gândește mult mai profund o problemă de combinatorică decât o face un elev de clasa a X-a care deja este prizonierul unor tipare și rezolvă cu ajutorul unor formule, pentru că „așa se face”, fără să aprofundeze fenomenul sau să înțeleagă de ce rezolvarea unei probleme se face cu formula respectivă. Nu trebuie însă să generalizăm. Sunt destui elevi de liceu care aprofundează acest domeniu pentru că stă la baza rezolvării unor probleme de programare. Nu trebuie însă să minimalizăm rolul pe care îl are pregătirea lor din clasele V-VIII pentru că logica și modul de abordare al acestor probleme atunci au fost formate.

Personal, consider că noțiunile primare de combinatorică pot face parte cu succes dintr-un manual de clasa a V-a sau a VI-a, fiind extrem de utile în dezvoltarea gândirii logice a viitorului liceean.

Lucrarea conține patru capitole: Cap I- Numere cardinale (teorie și exemple alături de cele trei principii de numărare), CapII – Elemente de combinatorică în care sunt prezentate principiul cutiei al lui Dirichlet, principiul elementului extremal, Cap III – Numerele lui Catalan ( care revin în forță în seturile de probleme propuse în concursurile școlare) alături de exemple sugestive si Cap IV care conține probleme diverse prin multitudinea de metode de rezolvare.

CAPITOLUL I

NUMERE CARDINALE

Noțiuni și rezultate teoretice fundamentale

Definiție: Fie și sunt douǎ mulțimi; ele se numesc cardinal echivalente sau echipotente dacǎ existǎ o funcție bijectivǎ.

Aceastǎ relație este o relație de echivalențǎ ȋn clasa tuturor mulțimilor iar clasele de echivalențǎ se numesc numere cardinale. Cardinalul mulțimii A se noteazǎ sau .

Dacǎ mulțimea A este finitǎ și numǎrul elementelor sale este n și este cardinal echivalentǎ cu B, atunci și mulțimea B are n elemente, și reciproc. Deci numǎrul cardinal este determinat de numǎrul de elemente din A. Astfel vom putea sǎ identificǎm cu numǎrul elementelor lui A. Scriem și de multe ori convenim sǎrecunoaștem urmatoarea:

Definiție: Cardinalul unei mulțimi este numǎrul elementelor acelei mulțimi.

Convenim ca .

Prin convenție , (alef zero). Orice mulțime cardinal echivalentǎ cu N se numește numǎrabilǎ. Orice mulțime finitǎ sau numǎrabilǎ se numește cel mult numǎrabilǎ.

Teorema de caracterizare a mulțimilor numǎrabile: O mulțime A este cel mult numǎrabilǎ dacǎ și numai dacǎ elementele sale se pot scrie sub formǎ de șir.

Dacǎ avem atunci funcția , este bijectivǎ, deci A este numǎrabilǎ. . Reciproc, dacǎ A este numǎrabilǎ atunci existǎ o funcție bijectivǎ si .

Reuniunea numǎrabilǎ de mulțimi numǎrabile este de asemenea o mulțime numǎrabilǎ. Ȋn particular, reuniunea unui numǎr finit de mulțimi numǎrabile este o mulțime numǎrabilǎ și reuniunea numǎrabilǎ de mulțimi finite este o mulțime cel mult numǎrabilǎ.

Pentru a demonstra aceastǎ afirmație considerǎm mulțimile numǎrabile

și considerǎm urmǎtorul tablou:

Obținem este șir.

EXEMPLU: Demonstrați cǎ Z și Qsunt mulțimi numǎrabile, scriind elementele sale sub formǎ de șir.

Demonstrație: Mulțimea iar

de unde concluzia.

Dacǎși sunt douǎ mulțimi, atunci vom scrie cǎ dacǎ A este cardinal echivalentǎ cu o submulțime a lui B. Relația este o relație de ordine totalǎ ȋn clasa tuturor numerelor naturale și este independentǎ de alegerea reprezentanților A și B.

Dacǎ este o mulțime finitǎ astfel ȋncȃt atunci mulțimea pǎrților lui A are elemente.

Dacǎ și sunt douǎ mulțimi finite astfel ȋncȃt și atunci : a) numǎrul funcțiilor este ;

b) dacǎ m=n atunci numǎrul funcțiilor injective (surjective, bijective) este ;

c) dacǎ atunci numǎrul funcțiilor injective este ;

d) dacǎ atunci numǎrul funcțiilor strict crescǎtoare (descrescǎtoare) este .

e) dacǎ numǎrul funcțiilor surjective este egal cu

.

Probleme

Se consideră mulțimea . Determinați numărul de triplete cu proprietatea că numerele sunt termeni consecutivi ai unei progresii aritmetice.

Rezolvare: Fie r rația progresiei

Deoarece

Cum .

Dacă și avem 2012 progresii aritmetice.

Dacă și avem 2010 progresii aritmetice.

Continuǎm procedeul:

Dacă și avem 4 progresii aritmetice.

Dacă și avem 2 progresii aritmetice.

Numărul total de triplete cu proprietatea din problemă este

.

2. GENERALIZARE: Fie n un numǎr natural, și . Determinați numărul de triplete cu proprietatea că numerele sunt termeni consecutivi ai unei progresii aritmetice.

O.M. Etapa județeanǎ, 2004

Rezolvare: Abordǎm problema asemǎnǎtor, dupǎ valorile pe care le poate lua rația progresiei. Dacǎ r este rația progresiei

Cum .

Dacă și avem progresii aritmetice (acestea sunt de forma ).

Dacă și avem progresii aritmetice (acestea sunt de forma ).

Continuǎm procedeul: dacǎ n este par , , rația maximǎ este și avem doar douǎ progresii aritmetice cu aceastǎ rație: .

Numǎrul total de progresii aritmetice ȋn acest caz este:

.

dacǎ n este impar , , rația maximǎ este și avem doar o progresie aritmeticǎ cu aceastǎ rație: .

Numǎrul total de progresii aritmetice ȋn acest caz este:

.

Pentru ambele situții putem scrie numǎrul total de progresii sub forma:

.

Ȋn fiecare pǎtrǎțel al unei table este scris cȃte un numǎr real. Emilia a calculat toate produsele de douǎ numere scrise ȋn pǎtrǎțele diferite ale tablei și a constatat cǎ exact 1000 dintre aceste produse erau negative. De cȃte ori apǎrea numǎrul 0 printre numerele cu care era completatǎ tabla? Gǎsiți toate rǎspunsurile posibile.

Concursul Nǎboj, Cehia și Slovacia, 2011

Rezolvare: Dacǎ p este numǎrul de numere pozitive și n numǎrul de numere negative din pǎtrǎțelele tablei, atunci și (ȋn tabel sunt de numere). n și p ȋndeplinesc condiția iar diferența reprezintǎ numǎrul de numere egale cu 0 din tabel. Obținem produse negative numai ȋnmulțind un numǎr pozitiv cu unul negativ, deci avem cu soluțiile (care nu respectǎ ) , , . Pentru ultimele douǎ, numǎrul de zerouri este , respectiv .

Dacă fie B mulțimea funcțiilor bijective

Pentru orice funcție , considerăm mulțimea .

Demonstrați că

Dacǎ sau , , arǎtați cǎ ,

Rezolvare: a) Evident . Pentru fiecare construim funcția . Atunci și deci , de unde concluzia.

b) Presupunem prin reducere la absurd că există cu

Atunci . Dar este impar pentru acele valori ale lui n din ipotezǎ. Cum și sumele și au aceeași paritate, obținem contradicție.

Considerăm un alfabet cu a litere și cu . Determinați numărul cuvintelor de lungime m, care conțin exact p litere distincte din alfabet.

Rezolvare: Pentru fiecare determinăm de fapt numărul funcțiilor surjective , unde și . Și cum cele p litere pot fi alese din alfabet în moduri, avem în total:

.

Un magician are 100 de cărți de joc, numerotate de la 1 la 100. El le pune în 3 cutii de culori diferite, astfel încât fiecare cutie să conțină cel puțin câte o carte de joc. Un spectator alege două din cele trei cutii, scoate câte o carte de joc din fiecare și anunță suma numerelor de pe cărțile de scoase. Știind această sumă, magicianul identifică cutia din care nu s-a scos nicio carte de joc.

În câte moduri pot fi așezate toate cărțile de joc în aceste cutii, astfel încât scamatoria magicianului să reușească întotdeauna? ( se consideră că două așezări sunt diferite dacă cel puțin o carte apare în cutii diferite)

Rezolvare: Trebuie să determinăm numărul de partiții ale mulțimii în trei submulțimi A, B, C, astfel ca să fie disjuncte (prin . Distingem două cazuri:

Există trei numere consecutive care aparțin unor clase diferite, adică există astfel ca . Cum , analog obținem și așa mai departe; evident dacă , etc.

Evident elementele celor trei mulțimi ale partiției sunt , , . Cum avem trei cutii de culori diferite vor fi moduri de a așeza cărțile în cutii.

Dacă nu există trei numere consecutive care să aparțină unor clase diferite, putem presupune că iar i este cel mai mic număr pentru care . Presupunem că , iar k este valoarea minimă pentru care . Avem de aici că . Presupunând , cum . , contradicție cu minimalitatea lui k. Deci singura valoare pentru k este 100 și . Demonstrăm că singura soluție este , și . Dacă mulțimea A ar conține un alt element x, cum absurd.

Ținând cont de permutările pe care le putem face cu cutiile colorate, vom avea încă 6 moduri de a așeza cărțile în cutii, de unde, în total, avem 12 moduri.

Propunem cȃteva exemple simple, selectate din variantele propuse de MEC pentru examenul de bacalaureat 2009.

Se considerǎ mulțimea . Sǎ se determine numărul submulțimilor cu trei elemente ale mulțimii A care conțin elementul 1. (Bacalaureat 2009)

Rezolvare: Cum fiecare submulțime conține elementul 1. Numărul submulțimilor cerute este dat de numǎrul submulțimilor de două elemente ale mulțimii adică

Sǎ se determine probabilitatea ca, alegând un numǎr din mulțimea numerelor de două cifre, sǎ avem . (Bacalaureat 2009)

Rezolvare: Numărul cazurilor posibile este dat de numerele de forma de două cifre și este 90.

Numărul cazurilor favorabile este dat de numărul numerelor unde și este 90 – 9 = 81. Probabilitate cerută .

Să se determine probabilitatea ca, alegând un număr din mulțimea numerelor naturale de trei cifre, acesta să aibă exact două cifre egale.

Rezolvare: Numărul cazurilor posibile este de 900. Numărul cazurilor favorabile este dat de numǎrul numerele de forma unde și . Pentru fiecare caz există numere. Numărul cazurilor favorabile fiind . Probabilitatea cerută este adică .

Să se determine numărul funcțiilor cu proprietatea că .

Rezolvare: Cum trebuie determinat numărul funcțiilor definite pe o mulțime cu trei elemente cu valori într-o mulțime cu patru elemente adică , deci 64 funcții.

Să se determine pentru care mulțimea are exact 120 de submulțimi cu două elemente. (varianta 7)

Rezolvare: Numărul de submulțimi cu două elemente a unei mulțimi cu n elemente, fiind de avem ecuația adică cu soluția număr natural n = 15.

Câte numere de patru cifre se pot forma cu elemente ale mulțimii {1, 3, 5, 7, 9}? Dar cu elemente ale mulțimii {0, 2, 4, 6, 8}? Câte numere de patru cifre distincte se pot forma cu cifre din mulțimea ?

Rezolvare: Numǎrul numerelor de patru cifre impare este numǎrul funcțiilor adicǎ numere.

Numǎrul numerelor de patru cifre pare este numǎrul funcțiilor cu adicǎ numere. adicǎ numere.

Numǎrul numerelor de patru cifre disticte este numere. Problema este echivalentǎ cu a determina numǎrul funcțiilor injective

Într-o clasă sunt 22 de elevi, din care 12 sunt fete. Să se determine în câte moduri se poale alege un comitet reprezentativ al clasei format din 3 fete și 2 băieți.

Rezolvare: În clasă sunt 10 băieți. Comitetul se poate se poate face în moduri.

Fie mulțimea A = {-2, -1, 0, 1, 2}. Să se determine numărul funcțiilor pare .(varianta 32)

Rezolvare:. Numărul funcțiilor este egal cu numărul permutărilor unei mulțimi cu 5 elemente, adică .

Fie mulțimea A = {1, 2, 3, 4, 5}. Să se determine numărul funcțiilor bjective cu proprietatea că .

Rezolvare: Numărul funcțiilor este egal cu numărul permutărilor unei mulțimi cu 4 elemente, adică .

Se consideră mulțimile A ={1, 2, 3, 4} și B= {1, 2, 3, 4, 5, 6}. Să se determine numărul funcțiilor strict crescătoare .

Rezolvare: . În total sunt 15 funcții strict crescătoare.

Se consideră mulțimile A = {1, 2, 3} și B = {1, 2, 3, 4, 5}. Să se determine numărul funcțiilor strict descrescătoare cu proprietatea că f(3)=1.

Rezolvare: Problema este echivalentǎ cu a determina funcțiile strict descrescătoare . Ȋn total funcții.

Se consideră mulțimea M = {0, 1, 2, 3, 4, 5}. Să se determine numărul tripletelor (a,b,c) cu proprietatea că .

Rezolvare: . Un triplet se poate ordona crescător într-un singur mod. Atunci numǎrul tripletelor este .

Se consideră mulțimea M a tuturor funcțiilor definite pe A ={1, 2, 3 } cu valori în . Să se calculeze probabilitatea ca, alegând o funcție din mulțime M, aceasta să fie injectivă. (varianta 67)

Rezolvare: Numărul funcțiilor ce se pot construi de la B este (cazuri posibile).

Numărul funcțiilor injective este același cu numărul funcțiilor bijective deoarece domeniul și codomeniul au același număr de elemente. Acesta este egal cu 6 (cazuri favorabile)

Se consideră dreptele paralele d1, d2 și punctele distincte A, B, C , M, N, P, Q. Să se determine numărul triunghiurilor care au toate vârfurile în mulțimea celor șapte puncte date.

Rezolvare:

A B C

X X X

x x x x

M N P Q

Este clar că vârful unui triunghi se află pe o dreaptă și baza pe cealaltă .

Triunghiuri cu vârful pe și baza pe

Fiecǎrui punct de pe ȋi corespund triunghiuri, total 18 triunghiuri

Triunghiuri cu vârf pe și baza pe

Fiecǎrui punct de pe ȋi corespund total 12 triunghiuri

Număr total de triunghiuri 18 + 12 = 30 triunghiuri.

Să se calculeze numărul diagonalelor unui poligon convex cu 8 laturi.

Rezolvare: numărul diagonalelor .

Cele trei principii de numărare

Principiul sumei

Dacă A și B sunt două mulțimi finite disjuncte, cardinalul reuniunii celor două mulțimi este suma cardinalelor celor două mulțimi .

Scriem

Generalizare: Cardinalul reuniunii a n mulțimi finite disjuncte două câte două este suma cardinalelor celor n mulțimi:

Exemple:1. a) Un triunghi echilateral cu latura de 3 cm este împărțit în triunghiuri echilaterale cu latura de 1cm, ducȃnd paralele la laturi. Câte triunghiuri echilaterale se obțin?

Rezolvare:

Notǎm cu A mulțimea triunghiurilor cu latura de 1cm, Card(A)=1+3+5=9,
cu B mulțimea triunghiurilor cu latura de 2cm, Card(B)=3,
C mulțimea triunghiurilor cu latura de 3cm, Card(C)=1
Atunci

b) Un triunghi echilateral cu latura de 4 cm este împărțit în triunghiuri echilaterale cu latura de 1cm, ducȃnd paralele la laturi. Câte triunghiuri echilaterale se obțin?

Rezolvare:

Dacǎ A este mulțimea triunghiurilor cu latura de 1cm, Card(A)=1+3+5+7=16;
B este mulțimea triunghiurilor cu latura de 2cm, Card(B)=1+2+3+1=7;
C este mulțimea triunghiurilor cu latura de 3cm, Card(C)=1+2=3
iar D este mulțimea triunghiurilor cu latura de 4cm, Card(D)=1
Atunci ;

c) Generalizare Un triunghi echilateral cu latura de n cm este împărțit în triunghiuri echilaterale cu latura de 1cm, ducȃnd paralele la laturi. Câte triunghiuri echilaterale se obțin?

Rezolvare: Notǎm cu numǎrul de triunghiuri echilaterale formate ȋn triunghiul de laturǎ n. Dacǎ triunghiul ABC are latura n+1, acesta va fi ȋmpǎrțit de dreptele paralele ȋn triunghiuri echilaterale de laturǎ 1.

Determinǎm o relație de recurențǎ pentru calculul lui numǎrȃnd triunghiurile care au cel puțin un vȃrf pe latura BC, (celelalte au fost numǎrate la ).

Triunghiurile cu douǎ vȃrfuri pe BC sunt ȋn numǎ de .

Triunghiurile cu un vȃrf pe BC

– de laturǎ 1 sunt ȋn numǎr de n;

– de laturǎ 2 sunt ȋn numǎr de n-2;

– de laturǎ 3 sunt ȋn numǎr de n-4 etc;

Discuția se poate face dupǎ cum n este par sau impar sau putem determina o relație de recurențǎ ȋntre și . Avem

Adunȃnd relațiile obținem

A

B C

Dacǎ este un poligon regulat cu n laturi, determinați numǎrul de triunghiuri obtuzunghice .

(propusǎ pentru O.B.M.J.)

Rezolvare: Studiem ȋn funcție de paritatea lui n:

Pentru par: triunghiurile obtuzunghice care au unghiul obtuz ȋn , . Numǎrul perechilor care ȋndeplinesc aceste condiții se calculeazǎ dȃndu-i lui j valori de la 2 la , cǎruia ȋi corespunde un numǎr k ales ȋn moduri. Numǎrul perechilor este : , iar numǎrul total al triunghiurilor este .

Pentru impar: triunghiurile obtuzunghice care au unghiul obtuz ȋn , ȋndeplinesc condiția . Numǎrul perechilor care ȋndeplinesc aceste condiții este : ,

iar numǎrul total al triunghiurilor este .

Se dau ȋntr-un plan 5 puncte. Printre dreptele care unesc aceste drepte cȃte douǎ, nu se aflǎ drepte paralele sau perpendiculare sau coincidente. Prin fiecare din punctele date se duc perpendiculare pe toate dreptele ce se pot construi cu celelalte patru puncte date.

Care este numǎrul maxim de puncte de intersecție a acestor perpendiculare, ȋn afara punctelor date?

(O.I.M. 1964)

Rezolvare: Fie cele 5 puncte date. Din se pot duce perpendiculare pe dreptele determinate de celelalte 4 puncte. Ȋn total vom avea 30 de drepte perpendiculare care se pot intersecta ȋn maxim puncte. Cum din se pot duce 6 perpendiculare, cele perpendiculare care se intersecteazǎ ȋn nu se numǎrǎ. Ȋn total scǎdem puncte. Perpendicularele din pe dreapta sunt paralele deci punctele lor de intersecție nu existǎ, prin urmare nu numǎrǎm puncte. Ȋn total avem drepte care sunt ȋn situația de mai sus deci trebuie sǎscǎdem 30 de puncte de intersecție.

Trebuie sǎ ținem cont și de faptul cǎ ȋntr-un triunghi ȋnǎlțimile sunt concurente și pierdem alte puncte de intersecție. Putem forma triunghiuri din care pierdem de puncte.

Avem cǎ numǎrul total de puncte de intersecție este .

Principiul includerii și al excluderii

Dacă A și B sunt două mulțimi finite, cardinalul reuniunii celor două mulțimi este suma cardinalelor celor două mulțimi din care se scade cardinalul intersecției lor.

Generalizare:

Principiul includerii și al excluderii generalizează principiul sumei, în sensul că dă formula de calcul a cardinalului reuniunii a două sau mai multe mulțimi finite în cazul general .

Exemple: 1. Câte numere naturale nenule, mai mici decât 1000, există astfel încât să fie multipli de 2 sau de 3? (Bacalaureat 2010)

Rezolvare: Dacă

2. Cei 32 de elevi ai unei clase s-au ȋnscris la cercurile de limbi strǎine. Astfel 17 fac englezǎ și 19 fac italianǎ. Cȃți dintre ei fac și englezǎ și italianǎ?

Rezolvare: Dacǎ A este mulțimea elevilor care fac englezǎ și B a celor care fac italianǎ avem și .

.

Principiul produsului

Cardinalul produsului cartezian a n mulțimi finite este produsul cardinalelor celor n mulțimi:

Exemple:

1. În câte moduri se poate alcătui meniul la o petrecere dacă avem de ales dintre 3 tipuri de aperitive, 5 feluri de friptură și 10 feluri de desert? Dar dacă ținem cont și de cele 6 salate diferite disponibile?

Rezolvare: ,

2. Câte numere de cinci cifre se pot forma doar cu cifrele impare? Dar cu cele pare?

Rezolvare:

Cu cifrele impare avem

Iar cu cele pare doar , deoarece excludem cifra 0 de pe primul loc.

Problema 3. Pe fiecare dintre fețele unui cub se scrie cȃte un numǎr natural nenul. Fiecǎrui vȃrf al cubului i se asociazǎ produsul numerelor scrise ȋn cele trei fețe care conțin respectivul vȃrf. Suma numerelor asociate celor opt vȃrfuri ale cubului este 2013. Care sunt valorile posibile ale sumei numerelor scrise pe cele șase fețe?

Concursul Nǎboj, Cehia și Slovacia, 2011

Rezolvare: Fie x; y; z numerele scrise pe cele trei fețe care conțin vȃrful A al cubului și cu m, n și respectiv p numerele scrise pe fețele opuse acestora (m și x sunt scrise pe fețe opuse și la fel y; n și z; p), atunci ȋn cele opt vȃrfuri ale cubului sunt scrise numerele xyz, xym, xnz, xnp, myz, myp, mnz și mnp.

Suma lor este . Deoarece sunt numere naturale mai mari ca 1, iar 2013 se descompune ca produs de trei numere naturale mai mari ca 1 ȋn mod unic atunci numerele sunt egale cu 3, 11 și 61 ( și permutǎri ale ale acestora), deci singura valoare posibilǎ a sumei .

Aceastǎ valoare se poate obține, de exemplu dacǎ pe fețele cubului scriem, pe perechi de fețe opuse, numerele 1 și 2, 5 și 6, 11 și 50.

O submulțime a mulțimii se numește specialǎ dacǎ nu conține nicio pereche de forma . O submulțime specialǎ se numește superspecialǎ dacǎ ea are numǎrul maxim posibil de elemente. Cȃte elemente are o submulțime superspecialǎ și cȃte submulțimi superspeciale existǎ?

Olimpiadǎ Finlanda, 2013

Rezolvare: Considerǎm submulțimile: Elementele acestor submulțimi sunt aranjate ȋn ordine crescǎtoare iar o submulțime specialǎ nu poate conține elemente consecutive ale niciuneia din mulțimi. Rezultǎ cǎ dintr-o submulțime specialǎ pot face parte: cel mult douǎ elemente (care nu pot fi numere consecutive) din mulțimile A1;A2;A3;A4 (neconsecutive) și cel mult un element din mulțimile A5;A6; …;A11. Pentru a obține o submulțime superspecialǎ, trebuie sǎ eliminǎ din mulțimea douǎ elemente din mulțimea A1 și cȃte unul din mulțimile A2; A3;…;A11, ȋn total 12 elemente.

Reciproc, dacǎ eliminǎm douǎ elemente din A1 astfel ca numerele rǎmase sǎ nu fi fost vecine (adicǎ sǎ eliminǎm 1 și 9, 3 și 9 sau 3 și 27), scoatem din mulțimile A2;A3;A4 numǎrul din mijloc (adicǎ 6, 12 și 15), iar din fiecare din mulțimile A5;A6;…;A11 cȃte un element, obținem o submulțime specialǎ cu 38 de elemente. Rezultǎ cǎ o submulțime specialǎ are cel mult 38 de elemente și existǎ astfel de submulțimi deci submulțimile superspeciale au 38 de elemente.

Acestea se obțin eliminȃnd din mulțimea urmǎtoarele elemente:

din mulțimea A1 eliminǎm 1 și 9, sau pe 3 și pe 9, sau pe 3 și pe 27 (trei posibilitǎți);

din A2 ȋl eliminǎm pe 6 (o posibilitate)

din A3 ȋl eliminǎm pe 12 (o posibilitate)

din A4 ȋl eliminǎm pe 15 (o posibilitate)

din A5 ȋl eliminǎm pe 7 sau pe 21 (2 posibilitǎți)

din A6 ȋl eliminǎm pe 8 sau pe 24 (2 posibilitǎți)

din A7 ȋl eliminǎm pe 10 sau pe 30 (2 posibilitǎți)

din A8 ȋl eliminǎm pe 11 sau pe 33 (2 posibilitǎți)

din A9 ȋl eliminǎm pe 13 sau pe 39 (2 posibilitǎți)

din A10 ȋl eliminǎm pe 14 sau pe 42 (2 posibilitǎți)

din A11 ȋl eliminǎm pe 16 sau pe 48 (2 posibilitǎți)

Conform regulii produsului vor fi de moduri, deci sunt 384 de mulțimi superspeciale.

CAPITOLUL I I

ELEMENTE DE COMBINATORICĂ

1. Denumirea de Ars Combinatoria este legatǎ de numele lui Ramon Llull (Raymond Lully) de origine catalanǎ, al lui Gotțried Leibniz cel care se bǎnuiește cǎ a dat numele disciplinei si metodelor și nu ȋn ultimul rȃnd de cel care a plasat-o ȋn fruntea disciplinelor matematice, Pál Erdös. Combinatorica se traduce ȋn manualele școlare prin metodele de numǎrare, denumire sugestivǎ la care ar trebui adǎugat cǎ tehnicile, gȃndirea și metodele se folosesc acum ȋn mai toate domeniile matematicii, indiferent cât de specializate sunt.

2. Metode

2.1. Principiul cutiei (pigeonhole principle). Este metoda cea mai cunoscutǎ, eficientǎ și simplǎ. Este cunoscut și ca principiul lui Dirichlet care nu este inventatorul ei ci doar cel care l-a evidențiat ȋntr-una din lucrarile sale de teoria numerelor.

Metoda spune ca dacǎ avem un numǎr de obiecte de așezat ȋntr-un numǎr mai mic de cutii atunci, evident, mǎcar una va conține cel puțin douǎ obiecte.

Putem extinde: a) dacǎ avem x obiecte și y cutii cu x > y și ȋn fiecare cutie am avea cel mult un obiect atunci ȋn cutii am avea cel mult y obiecte care vor fi repartizate ȋn cutii, deci existǎ o cutie ȋn care avem cel puțin obiecte.

b) dacǎ avem un numǎr infinit de obiecte atunci mǎcar una dintre cutii va conține un numǎ infinit de obiecte.

c) (argument de medie-Littlewood) dacǎ n variabile cu valori pozitive au suma S (sau produsul P) atunci mǎcar una este mai micǎ sau cel mult egala cu (respectiv ).

Vom prezenta ȋn cele ce urmeazǎ tipuri de probleme care se rezovǎ cu principiul cutiei.

Probleme

Arǎtați cǎ oricum am alege 7 numere existǎ printre ele cel puțin douǎ care au proprietatea cǎ diferența pǎtratelor lor este divizibilǎ cu 10.

Rezolvare: Oricum am alege aceste numere ele au proprietatea cǎ pǎtratele lor au ultima cifrǎ ȋn mulțimea . Deci avem doar 6 cutii și 7 numere. Rezultǎ cǎ cel puțin douǎ dintre numerele considerate au aceeași ultimǎ cifrǎ de unde diferența lor va fi un numǎr divizibil cu 10.

La o conferințǎ participǎ 30 de persoane. Arǎtați cǎ printre participanți existǎ  douǎ  persoane care au același numǎr de cunoștințe.

Rezolvare: O persoanǎ  poate avea 0, 1, 2,…, 29 de cunoștințe printre participanții la conferințǎ. Acestea pot fi identificate cu numǎrul de cutii. Dacǎ o persoanǎ are 0 cunoștințe printre participanți atunci nu existǎ nicio persoanǎ care are 29 de cunoștințe, deci cutiile care conțin 0 și 29 nu pot fi ocupate în același timp. Rǎmân 29 de cutii și 30 de persoane. Deci existǎ douǎ persoane care au același numǎr de cunoștințe.

Generalizare: La o petrecere sunt invitate n persoane. Fiecare dintre acestea cunoaște un numǎr de alte persoane invitate. Se știe cǎ dacǎ A cunoaște pe B,atunci și B cunoaște pe A. Sǎ se determine dacǎ existǎ douǎ persoane care au același numǎr de cunoștințe printre cele invitate la petrecere.

Rezolvare: Fiecare persoanǎ cunoaște cel puțin 0 persoane și cel mult n – 1 persoane. Dacǎ existǎ o persoanǎ care le cunoaște pe toate celelalte n – 1 persoane, atunci nu va exista o persoanǎ care sǎ nu cunoascǎ nici o altǎ persoanǎ dintre invitați. Dacǎ existǎ o persoanǎ care nu cunoaște pe nimeni atunci nu va exista o persoanǎ care sǎ cunoascǎ pe toate celelalte n – 1 persoane din camerǎ. Mulțimea numerelor corespunzǎtoare numǎrului de persoane cunoscut de fiecare invitat este formatǎ din cel mult n – 1 valori distincte (dacǎ îl conține pe 0, atunci nu îl conține pe n – 1, iar dacǎ îl conține pe n – 1 nu îl conține pe 0). Cu avem n persoane, înseamnǎ cǎ cel puțin douǎ dintre ele cunosc un același numǎr de persoane printre invitați.

Observație: Problema poate fi reformulatǎ ȋn limbaj de teoria grafurilor

Sǎ se arate cǎ într-un graf neorientat existǎ douǎ vârfuri care au același grad.

Pe aceeași temǎ putem reformula:

La un campionat de fotbal participǎ n echipe. Regula este: oricare douǎ joacǎ o singurǎ datǎ. Sǎ se arate cǎ în orice moment existǎ douǎ echipe care au jucat același numǎr de partide.

Rezolvare: La un moment dat fiecare echipǎ a jucat cel puțin 0 jocuri, dar nu mai mult de n – 1. Dacǎ existǎ o echipǎ care a jucat n – 1 jocuri, atunci nu existǎ o echipǎ care sǎ nu fi jucat nici un joc. Dacǎ existǎ o echipǎ care nu a jucat nici un joc, atunci nicio echipǎ nu a jucat toate cele n – 1 jocuri. Formǎm mulțimea numerelor care constituie numǎrul de partide jucate de fiecare echipǎ (cutiile), atunci aceasta va conține cel mult n – 1 numere (dacǎ îl conține pe 0, atunci nu îl conține pe n – 1, iar dacǎ îl conține pe n – 1 nu îl conține pe 0). Cum sunt n echipe, avem cǎ cel puțin douǎ dintre ele au jucat acela și numǎr de jocuri.

Fie A o mulțime cu n elemente. Sǎ se arate cǎ, dacǎ alegem mai mult decât jumǎtate dintre submulțimile mulțimii A, atunci douǎ dintre acestea au proprietatea cǎ una este inclusǎ în cealaltǎ.

Rezolvare: Mulțimea pǎrților unei mulțimi cu n elemente, are elemente.

Dacǎ și B = A\{a}, pentru fiecare submulțime X a lui B vom forma perechea

. Aceste perechi formeazǎ o partiție a mulțimii A. Dacǎ alegem mai mult de jumǎtate dintre submulțimile lui A, conform principiului cutiei, vor exista douǎ care se aflǎ în aceeași pereche. Douǎ mulțimi din aceeași pereche au proprietatea cǎ una este inclusǎ în cealaltǎ.

Arǎtați cǎ oricum am alege 81 de numere naturale ale cǎror divizori primi se aflǎ ȋn mulțimea , existǎ patru al cǎror produs este puterea a patra a unui numǎr natural. (Gazeta matematicǎ nr 11-2013)

Rezolvare: Cele 81 de numere sunt de forma . Cum i, j și k sunt pare sau impare vom avea 2x2x2 = 8 tipuri de numere. Grupǎm aceste numere ȋn 9 mulțimi de cȃte 9 numere. Conform principiului cutiei, ȋn fiecare mulțime existǎ cel puțin douǎ cu proprietatea cǎ i, j și k au aceeași paritate. Avem mai departe cǎ produsul lor este un pǎtrat perfect, adicǎ exponenții lui 2, 3 respectiv 5, sunt numere pare. Am obținut cel puțin nouǎ astfel de numere, din fiecare mulțime inițialǎ cel puțin unul, ai cǎror exponeți, dau la ȋmpǎrțirea cu 4 resturile 0 sau 2. Din nou avem 8 tipuri de numere deci existǎ cel puțin douǎ cu proprietatea exponenții celor trei factori dau, respectiv, același rest la ȋmpǎrțrea cu 4. Produsul celor douǎ va avea proprietatea cǎ exponenții lui 2, 3 respectiv 5 vor fi numere divizibile cu 4 de unde concluzia problemei.

Fie . a) Sǎ se arate cǎoricum am alege 5 de numere din M, existǎ douǎ al cǎror produs sǎ fie pǎtrat perfect.

b)Sǎ se arate cǎ oricum am alege 25 de numere din M, existǎ 4 al cǎror produs este puterea a 4-a a unui numǎr natural. (concurs Arhimede, etapa a II-a, martie 2014)

Rezolvarea presupune același procedeu ca mai sus. Pentru a) din cele 5 numere existǎ cel puțin douǎ ale cǎror exponenți au respectiv, aceeași paritate și deci produsul lor e un pǎtrat perfect. Pentru b) grupǎm numerele ȋn 5 mulțimi și aplicǎm din nou pricipiul cutiei.

Arǎtați cǎ numǎrul 2013 are un multiplu de forma 1111…11.

Rezolvare: Fie numerele 1, 11, 111, …, Avem 2013 numere pe care, dacǎ  le împǎrțim la 2013 obținem 2013 resturi. Printre ele, conform principiului cutiri, existǎ cel puțin douǎ numere care dau același rest prin împǎrțire la 2014. Atunci diferența lor se divide prin 2013, deci exista m și n numere naturale mai mici decȃt 2014, m>n astfel ca .

Cum adicǎ este un multiplu al lui 2013.

Vom considera un pǎtrat și nouǎ linii, fiecare dintre ele tǎind pǎtratul dat în douǎ patrulatere de arii proporționale cu 2/3. Sǎ se arate cǎ existǎ trei linii care trec prin același punct.

Rezolvare: Notǎm vârfurile pǎtratului cu A, B, C, D în sensul invers trigonometric.

A B

M

N

D C

Evident cǎ nici una dintre linii nu poate tǎia douǎ laturi consecutive ale pǎtratului altfel am obține un triunghi și un pentagon și nu un patrulater. Sǎ presupunem cǎ una dintre linii intersecteazǎ laturile BC și AD în punctele M, respectiv N. Patrulaterele ABMN și CDNM sunt, evident, trapeze având aceeași înǎlțime. Ariile lor sunt în același raport în care se aflǎ și liniile lor mijlocii. Deci, MN intersecteazǎ linia mijlocie a pǎtratului într-un punct care o ȋmparte ȋn douǎ segmente al cǎror raport este 2/3. Afirmația este adevǎratǎ pentru oricare dintre cele nouǎ secante. Dar existǎ doar patru puncte care împart liniile mijlocii ale pǎtratului în raportul 2/3. Conform principului cutiei, cel puțin trei linii trec prin același punct.

Fie 25 de puncte în plan cu proprietatea cǎ pentru oricare trei puncte dintre ele existǎ o pereche de puncte aflate la o distanțǎ mai micǎ de o unitate. Sǎ se arate cǎ existǎ un cerc de razǎ o unitate care conține 13 puncte dintre cele 25.

Rezolvare: Alegem la întâmplare un punct (pe care îl notǎm cu A) dintre cele 25 date și considerǎm cercul C(A, 1) având centrul în A și raza o unitate. Dacǎ toate punctele (sau cel puțin 13) ar fi în cercul considerat, atunci problema este rezolvatǎ; altfel, considerǎm un alt punct B care nu se aflǎ în C(A, 1) (deci distanța între A și B este mai mare de o unitate). Pentru orice alt punct C, fie distanța dintre A și C este mai micǎ de o unitate, fie distanța dintre B și C este mai micǎ de o unitate. Deci fiecare dintre punctele rǎmase aparțin fie cercului cu centrul în A și razǎ o unitate, fie cercului cu centrul în B și razǎ o unitate. Conform principiului

cutiei, în interiorul unuia dintre cercuri se vor afla cel puțin 13 puncte.

Fie cinci puncte în plan, având coordonate numere întregi. Sǎ se arate cǎ unul dintre mijloacele segmentelor care unesc cele cinci puncte are, de asemenea, coordonatele întregi.

Rezolvare: Fiecare punct din cele cinci este de forma A(x, y), cu x și y numere întregi. Conform principiului cutiei trei dintre cele cinci abscise ale punctelor date au aceeași paritate. Dintre acestea existǎ douǎ (tot conform principiului cutiei) ale cǎror ordonate au aceeași paritate. Mijlocul segmentului care unește aceste douǎ

puncte are coordonatele numere întregi (media aritmeticǎ a douǎ numere de aceeași paritate este întotdeauna un numǎr întreg).

Altfel: existǎ variante pentru alegerea coordonatelor celor cinci puncte dupǎ cum numerele respective sunt pare sau impare. Conform principiului cutiei,

existǎ douǎ puncte ale cǎror coordonate au aceeași paritate (x și y ambele pare sau impare). De aici, mijlocul segmentului care leagǎ cele douǎ puncte are coordonatele întregi.

Se considerǎ un cerc cu raza de o unitate și șase puncte în interiorul sǎu. Sǎ se arate cǎ existǎ douǎ puncte la o distanțǎ de cel mult o unitate.

Rezolvare: Împǎrțim cercul în șase sectoare egale astfel încât unul dintre punctele date (fie el A) sǎ se afle pe una dintre cele șase raze considerate. Distanța dintre oricare douǎ puncte din același sector este cel mult o unitate. Dacǎ într-unul dintre cele douǎ sectoare în care este inclus punctul A se mai aflǎ încǎ un punct, atunci problema este rezolvatǎ. Altfel, mai rǎmân patru sectoare în care se aflǎ cinci puncte . Conform principiului cutiei, existǎ cel puțin un sector în care vom avea douǎ puncte. Cele douǎ puncte din același sector se aflǎ la o distanțǎ mai micǎ sau egalǎ cu o unitate unul fațǎ de celǎlalt.

Demonstrați că orice poliedru convex are două fețe cu același număr de laturi.

Rezolvare: Fie o față a poliedrului cu număr maxim de laturi. Deci orice altă față are cel mult n laturi. Dacă mai există o față cu n laturi problema e rezolvată. Altfel fețele poligonului ar avea 3, 4, 5, …sau n-1 laturi. Deci cele n fețe vecine feței au doar n-3 moduri de atribuire a unui număr de laturi. Rezultă că cel puțin două au același număr de laturi.

La o competiție sportivǎ  participǎ 201 elevi din cinci școli. Știind cǎ în fiecare grup de șase elevi, cel puțin doi elevi sunt de aceeași vârstǎ , arǎtați cǎ  existǎ  cel puțin cinci elevi de la aceeași unitate școlarǎ , de aceeași vârstǎ  și de același sex. (Concurs Viitori Olimpici 2014)

Rezolvare: Ȋn grupul celor 201 elevi participanți cel puțin 101 elevi sunt de același sex (201 = 2 ˑ100 + 1) . Ȋn fiecare grup de șase elevi, cel puțin doi elevi sunt de aceeași vârstǎ , deci în grupul elevilor participanți gǎsim cel mult cinci vârste diferite. Astfel cǎ  în grupul celor 101 elevi de același sex, avem 21 elevi cu aceeași vârstǎ (101 = 5ˑ20 + 1). Iar cum elevii provin de la cinci unitǎți școlare diferite, în grupul de 21 elevi de același sex și cu aceeași vârstǎ, vom avea 5 elevi care provin de la aceeași școalǎ  (21 = 5 ˑ4 + 1).

2.2. Principiul elementului extremal este metoda prin care se poate deduce o proprietate specialǎ (foarte des maximalitate sa sau minimalitate relativ la o mǎsurǎ oarecare, cum ar fi valoare, distanțǎ etc.), analizȃnd totalitatea obiectelor, sau totalitatea configurațiilor ce se pot realiza pornind de la datele unei probleme.

PROBLEME

Se consideră cinci numere naturale a, b, c, d, e care nu se divid cu 5. Arătați că se pot alege câteva dintre ele cu suma divizibilă cu 5.

Rezolvare: Presupunem prin absurd că oricum am alege câteva numere, suma lor nu este un număr divizibil cu 5. Atunci numerele:

pot da unul din resturile 1, 2, 3, 4 la împărțirea cu 5. Cum avem 5 sume și 4 resturi rezultă că cel puțin două dintre ele dau același rest la împărțirea cu 5 deci diferența lor este multiplu de 5, adă există cîteva a căror sumă este divizibilă cu 5.

Generalizare: Fiind date n numere ȋntregi (nu neapǎrat distincte), sǎ se arate cǎ existǎ unele dintre ele a cǎror sumǎ este divizibilǎ cu n.

Rezolvare: Practic am avea moduri de alege mulțimi de numere din cele n date mult prea multe cazuri de rezolvat dacǎ ar fi sǎ cercetǎm fiecare situație ȋn parte. Cu aceste n numere putem face n+1 sume diferite. Astfel, dacǎ sunt numerele date considerǎm:

.

Conform principiului cutiei, existǎ printre ele, cel puțin douǎ care dau același rest la ȋmpǎrțirea cu n. Diferența celor douǎ sume va fi un numǎr divizibil prin n și evident este o sumǎ a unor numere din cele n date.

Observație

Dacǎ modificǎm enunțul problemei și considerǎm 2n-1 numere ȋntregi sǎ se arate cǎ existǎ n dintre ele astfel ȋncȃt suma lor sǎ fie divizibilǎ prin n. (Erdös-Ginzburg-Ziv).

Pentru n=2 problema devine: Dacǎ alegem 3 numere ȋntregi (nu neapǎrat distincte), sǎ se arate cǎ existǎ 2 dintre ele astfel ȋncȃt suma lor sǎ fie divizibilǎ prin 2 (parǎ), demonstrația fiind evidentǎ.

Pentru n=3 enunțul devine: Dacǎ alegem 5 numere ȋntregi (nu neapǎrat distincte), sǎ se arate cǎ existǎ 3 dintre ele astfel ȋncȃt suma lor sǎ fie divizibilǎ prin 3. Rezolvarea presupune mai douǎ cazuri: dacǎ printre cele 5 existǎ 3 care dau același rest la ȋmpǎrțirea cu 3 atunci suma lor, evident, este multiplu de 3, altfel, existǎ 3 numere care dau resturi diferite la ȋmpǎrțirea cu 3 deci suma lor este multiplu de 3.

Pentru n=6,fiind date 11 numere ȋntregi (nu neapǎrat distincte sǎ se arate cǎ existǎ 6 dintre ele astfel ȋncȃt suma lor sǎ fie divizibilǎ prin 6.

Rezolvare: Fiind date putem presupune cǎ este parǎ., presupune este parǎ, …, este parǎ. Dintre cele cinci sume ȋntregi pare putem gǎsi trei cu suma divizibilǎ prin 3. Dar suma acestor trei este egalǎ cu suma celor 6 numere care le formeazǎ, de unde rezolvarea problemei..

Particularizȃnd pentru fiecare n vom obține rezultate similare.

Demonstrați cǎ este irațional.

Rezolvare: Fie (), cu n minimal.

Cum ,

Cum ceea ce contrazice alegerea minimalǎ a lui n.

(Teorema lui Fermat) Fie p un numǎr prim, și a un ȋntreg pozitiv astfel ca (a,p)=1. Atunci p divide numǎrul

Rezolvare: Fie numerele a, 2a, . . . , (p − 1)a, evident fiecare fiind prim cu p. Pentru oricare douǎ dintre ele diferența este un numǎr prim cu p, ceea ȋnseamnǎ cǎ cele p − 1 numere dau resturi disticte și nenule la ȋımpǎrțirea prin p, deci aducǎ toate resturile de la 0 la p-1. Rezultǎ cǎ produsul lor și dau același rest la ȋmpǎrțirea prin p deci p divide diferenșa lor de unde .

Fiind dat un poligon convex cu 9 vârfuri ȋın plan, sǎ se arate cǎ existǎ douǎ diagonale care fac ȋıntre ele un unghi mai mic de 7o.

Rezolvare:: Numǎrului de diagonale este .

Fie P un punct oarecare ȋn plan prin care ducem câte o dreaptǎ paralelǎ la fiecare dintre diagonale. Dacǎ douǎ diagonale sunt paralele, problema este rezolvatǎ deoarece unghiul facut ȋıntre ele este 0◦. Dacǎ nu, ȋın jurul lui P s-au format 54 semidrepte (câte douǎ pentru fiecare diagonalǎ), care ȋımpart cele 360◦ grade din jurul lui P ȋın 54 de unghiuri. Cel puțin unul dintre unghiurile formate ȋıntre douǎ semidrepte consecutive va fi cel mult .

Se dau 20 de numere naturale nenule distincte mai mici decât 70. Sǎ se arate cǎ existǎ  4 perechi de numere dintre cele 20 a cǎror diferențǎ  este aceeași.(Concurs Viitori Olimpici 2014)

Rezolvare: Fie numerele date. Putem considera cǎ . Trebuie sǎ demonstrǎm cǎ printre ele existǎ patru perechi care dau aceeași diferențǎ . Avem:

. Presupunem cǎ  printre cele 19 diferențe, cel mult 3 au valori egale. Avem: – contradicție. Deci avem patru diferențe egale.

4. Numerele lui Fibonacci.

Fie , numărul submulțimilor mulțimii care nu conțin numere întregi consecutive.

Se obține șirul (prin definiție),

Numerele se numesc numerele lui Fibonacci și verifică relația

cu și . Urmând agoritmul de rezolvare al relațiilor de recurență liniare de ordinul II, se obține:

.

Exemplu:

La un concurs prezidat de împăratul Germaniei, Frederick al II-lea, Fibonacci a răspuns la următoarea problemă, propusă chiar de împărat: Plecând de la o singură pereche de iepuri și știind că fiecare pereche de iepuri produce în fiecare lună o nouă pereche de iepuri, care devin productivi la vârsta de o lună, calculați cîte perechi de iepuri vor fi după n luni. ( Se consideră că iepuriinu mor în decursul respectivei perioade de n luni).

Rezolvare: Din problemă rezultă că numerele perechilor de iepuri existent în fiecare lună sunt termeni consecutivi ai șirului lui Fibonacci.

Presupunem ca la 1 ianuarie avem o singură pereche de iepuri care corespunde lui . Aceasta face o pereche de iepuri la 1 februarie deci acum sunt două perechi, număr care corespunde lui .

La 1 martie, prima pereche mai face o pereche de pui. Avem acum , iar la 1 aprilie vor face pui și prima și cea de-a doua pereche care a devenit acum productivă, acestea adunându-se celor trei deja existente. Avem acum .

Deci la fiecare lună numărul perechilor creste cu un număr egal cu suma dintre perechile existente cu o luna în urmă și cele existente cu două luni în urmă și care acum au devenit toate productive. Matematic scriem

În câte moduri se poate pava un dreptunghi de dimensiuni cu plăci dreptunghiulare de dimensiuni ?

REZOLVARE: Fie numărul căutat cu . Evident , , . La fiecare nouă linie de dimensiuni 2×1 adăugată, completăm de fapt pavarea precedentă cu pavarea obținută cu doi pași în urmă obținând de fapt recurența din șirul lui Fibonacci.

CAPITOLUL III

NUMERELE LUI CATALAN

Numerele pe care le vom defini în continuare au apărut ca o consecință a rezolvării unor probleme de combinatorică. Numele provine de la matematicianul belgian Eugene Charles Catalan (1814 – 1894). Acesta le-a obținut în încercarea de a rezolva o problemă legată de distribuția parantezelor la înmulțire, făcând observațiile din tabelul următor:

Definiție: Numerele se numesc numerele lui Catalan.

Vom demonstra cǎ aceste numere sunt numere naturale. Pentru aceasta avem nevoie de un rezultat mai general care aparține lui Hermite.

Teoremă: Dacǎ , atunci numǎrul se divide cu , unde este cel mai mare divizor comun al numerelor m+1 și n.

Demonstrație: Notǎm deci existǎ astfel ca

Cum avem

.

Cum este numǎr natural rezultǎ concluzia teoremei.

Primele numere ale lui Catalan sunt:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,…

Istoria le consemneazǎ de fapt prima datǎ ȋn scrierile matematicianului chinez Ming în jurul anului 1730, dar este mult mai cunoscut rezultatul lui Euler (1751)

Probleme:

Câte posibilități de triangularizare a unui poligon convex cu n laturi există? (Concurs Viitori Olimpici 2014)

Rezolvare: Figura de mai jos sugereazǎ ideea că se obțin aceleași numere ca în problema studiată de Catalan.

Soluția prezentatǎ de Euler prin inducție demonstreazǎ următoarea formulă:

.

Se obține .

Au loc de asemenea urmǎtoarele rezultate:

.

.

Demonstrație:

Pe un cerc se consideră 2n puncte distincte, unde n este numǎr natural. În câte moduri putem construi n coarde ale cercului, care nu se intersectează, prin unirea două câte două a celor 2n puncte?

Rezolvare: Vom demonstra prin inducție că numărul căutat este numărul lui Catalan adicǎ .

Pentru n=1 există un singur mod de a uni cele douǎ puncte. Avem și , deci propoziția se verificǎ.(fig.1)

fig.1 fig.2

Pentru n=2 avem patru puncte pe care le putem uni în două moduri (fig.2):

Avem

Arătăm că dacă propoziția e adevărată pentru orice atunci va fi adevărată și pentru

Fie două puncte care, unite printr-o coardǎ, le separă pe celelalte în două grupuri cu număr par de puncte (nord și sud). Există următoarele posibilități: să nu rămână nicio pereche în nord și celelalte n-1 perechi în sud, o pereche în nord și n-2 perechi în sud, … , n-1perechi în nord și nicio pereche în sud. Să presupunem că la nord față de cele două puncte considerate sunt k perechi și atunci în sud vor fi perechi. Aceste două grupe vor forma coarde independent una de alta, deci conform ipotezei inducției în cea din nord vom avea modalități, iar în cea din sud modalități, deci pentru acest caz în total modalități de a desena coarde. Adunȃnd aceste numere obținem , ceea ce trebuia demonstrat.

Calculați numărul de drumuri laticiale crescătoare de la (0, 0) la (n, n) , care nu trec deasupra diagonalei principale. Un drum este crescător dacă la fiecare pas deplasarea se face sau la dreapta (D) sau în sus (S).

Rezolvare: Ȋn schemele de mai jos sunt descrise drumurile posibile, având sensul de deplasare indicat printr-o secvențȃ de 2n litere, în care D apare de n ori și S apare de n ori. Este evident că orice drum corect trebuie să înceapă cu o deplasare la dreapta și să se finalizeze cu o deplasare în sus, adică secvența care corespunde începe cu D și se sfârșește cu S. În plus, în fiecare moment al deplasării, numărul pașilor făcuți spre dreapta trebuie să fie mai mare sau egal decât cel al pașilor făcuți în sus, condiție ce se impune pentru a nu trece de diagonala principală.

Convenim că o secvențǎ are proprietatea (p), dacă este format din n litere D și n litere S, astfel încât să înceapă cu D și să se termine cu S, iar pentru orice în primele k litere ale cuvântului numărul aparițiilor lui D este cel puțin egal cu numărul aparițiilor lui S.

Am arătat că oricărui drum corect îi corespunde o secvențǎ cu proprietatea (p). Reciproc, oricărui cuvânt cu proprietatea (p) îi corespunde un drum corect, deci numărul drumurilor corecte este egal cu numărul secvențelor cu proprietatea (p).

Calculul numerelor se poate face cu ușurință prin însumări repetate, ca în tabelul de mai sus.

Deoarece numărul de pași care trebuie făcuți pentru a ajunge din (0,0) în (n,n) este, din care n spre dreapta, iar n în sus, deducem că există drumuri posibile dintre care însă o parte sunt incorecte (trec deasupra diagonalei principale).

Analizând în tabelul următor

raportul dintre numărul tuturor drumurilor posibile din (0,0) în (n,n) și numărul drumurilor valide, constatăm că de unde intuim formula .

Calculǎm câte drumuri sunt invalide. Orice drum invalid are un moment în care numărul de pași făcuți în sus este cu 1 mai mare decât numărul de pași făcuți spre dreapta. Să presupunem că acesta este pasul 2k+1; atunci avem k pași făcuți spre dreapta și k+1 pași făcuți în sus. Au rǎmas de fǎcut n-k pași spre dreapta și n-k-1în sus. La drumul rămas schimbăm sensurile între ele, ceea ce înseamnă că vom mai face n-k pași în sus și n-k-1 spre dreapta. Fiind în total n+1 pași în sus, am depășit ordonata n. Această transformare arată că există o bijecție între numărul drumurilor invalide și cel al drumurilor cu n+1 pași în sus, deci vor fi drumuri invalide. Ca urmare scăzând din numărul drumurilor posibile pe cel al drumurilor invalide, aflăm numărul drumurilor valide:

.

Observație: Regȃndim problema precedentǎ dupǎ acest algoritm. Desenăm coardele de tipul cerut prin unirea două câte două a celor 2n puncte de pe cerc, obținând n coarde care nu se intersectează. Mergem în jurul cercului, pornind dintr-un punct oarecare ales, într-unul din sensuri. Atunci când întâlnim o coardă pentru prima dată, îi etichetăm capătul cu D. Atunci când o întâlnim a doua oară etichetăm cu S. Obținem astfel secvențe cu proprietatea (p). Constatăm că oricărui cuvânt cu proprietatea (p) îi corespunde în mod unic o secvențǎ de n coarde cu proprietatea cerută. (În parcurgerea cuvântului de la stânga la dreapta, asociem fiecărei litere S ultima literă D pentru a forma perechea de puncte ce determină o coardă.) Am construit astfel o bijecție între numărul de moduri în care putem construi n coarde valide și numărul drumurilor valide de la (0, 0) la (n, n). Ca urmare, cele două probleme au același rezultat: .

Exemplu : n=3

Doi luptători kung-fu, Pai și Hai, se provoacă la o luptă pe butuci. Punctele din figurǎ reprezintă pozițiiile butucilor, pe fiecare linie și pe fiecare coloană existând câte 2013 butuci. Inițial, Hai se află ȋn punctul H, iar Pai ȋn punctul P.

La fiecare semnal al unui arbitru, fiecare luptător sare pe un butuc vecin astfel: Pai sare spre nord sau spre est, iar Hai sare spre sud sau spre vest. Care este probabilitatea ca cei doi luptători să se ȋntȃlnească pe unul dintre butuci? Rezolvare: Considerăm un reper cartezian cu originea ȋn P, PR fiind axa Oy, PG fiind axa Ox. Să studiem numărul de cazuri ȋn care cei doi se ȋntȃlnesc. Fie x numărul de pași pe care ȋl face Pai, pȃnă la ȋntȃlnirea cu Hai. Evident, și Hai a făcut tot x pași. Ȋn momentul ȋn care se ȋntȃlnesc, aceștia realizează un drum complet de la P la H. Lungimea unui astfel de drum, numit drum minim, este , de unde x = 2012. Dar făcȃnd 2012 pași fiecare, aceștia ajung pe diagonala RG, deci se ȋntȃlnesc pe diagonala RG.

Rămȃne să numărăm numărul de drumuri minime de la P la H (cazuri favorabile) și numărul de drumuri diferite pe care Pai și Hai pot să le facă pȃnă la diagonala secundară, nefiind neapărată nevoie să se ȋntȃlnească (cazuri posibile).

Numărăm mai ȋntȃi numărul de drumuri minime din P(0; 0) ȋn H(2012; 2012).

Să tratăm cazul mai general, să aflăm numărul drumurilor laticeale de lungime

minimă care unesc punctul O(0; 0) cu punctul B(m; n), . Lungimea minimǎ a unui astfel de drum este m + n, singurele deplasări fiind de forma sau . Din cei m + n pași de lungime 1 avem de făcut m pași orizontali și n pași verticali, ordinea efectuării lor fiind arbitrară. Numărul drumurilor laticeale cerut este egal cu numărul de pași pe orizontală adicǎ moduri. Ȋn cazul de față m = n = 2012, de unde numărul de drumuri minime, egal cu numărul de cazuri favorabile, este. (1)

Pai și Hai se pot ȋntȃlni doar după 2013 pași, pe diagonala RG, deci avem posibilității pentru fiecare, ȋn total cazuri posibile. (2)

Ți in^and cont de (1) și (2), probabilitatea este .

CAPITOLUL IV

PROBLEME

Cȃte dreptunghiuri se pot numǎra ȋn figura 1?

Rezolvare: Fǎrǎ a restrȃnge generalitatea problemei, presupunem cǎ cele mai mici dintre dreptunghiuri sunt pǎtrate unitate. Considerǎm, mai ȋntȃi, cazul mai general, ȋn care figura este formatǎ din m x n pǎtrate unitate, adicǎ un dreptunghi cu baza m și ȋnǎlțimea n.

Dacǎ m = n = 1, atunci avem un singur dreptunghi

Dacǎ m = 2; n = 1, numǎrǎm 1+2 = 3 dreptunghiuri .

Dacǎ m = 3; n = 1, numǎrǎm 1+2+3 dreptunghiuri. Ȋn general, ȋntr-un șir de m pǎtrate unitate se pot numǎra 1 + 2 + … +m dreptunghiuri, adicǎ pentru un pǎtrat unitate ȋn plus se formeazǎ fatǎ de cele numǎrate anterior ȋncǎ m dreptunghiuri noi (el, și combinații ale lui cu un vecin, doi vecini, …, (m-1) vecini).

Dacǎ m = 1; n = 2, avem 1 + 2 dreptunghiuri;

dacǎ m = 2; n = 2, atunci avem (1 + 2)(1 + 2) = 9 dreptunghiuri ;

dacǎ m = 3; n = 2, atunci numǎrǎm (1 + 2 + 3)(1 + 2) dreptunghiuri.

Ȋn general, pentru o figurǎ cu m x n pǎtrate unitate formȃnd un dreptunghi m x n, avem (1 + 2 + … + m)(1 + 2 + … + n) dreptunghiuri formate, deoarece fiecare linie adǎugatǎ, fie numǎrul ei de ordine k, aduce la cele p de dinainte ȋncǎ pk dreptunghiuri nou formate. Atunci ȋntr-un dreptunghi m x n format din pǎtrate unitate numǎrǎm (1 + 2 + … + m)(1 + 2 + … + n) = n(n+1)m(m+1)/4 dreptunghiuri.

Considerǎm notațiile din figurǎ.

Notǎm cu S1 mulțimea dreptunghiurilor din figura ABCD, cu S2 mulțimea dreptunghiurilor din figura XY PQ și cu S3 multțmea dreptunghiurilor din TZNM. Atunci, din principiul includerii și excluderii numǎrul cǎutat este

Deci numǎrǎm 690 dreptunghiuri ȋn figurǎ.

Un tablou dreptunghiular cu m linii și n coloane este completat cu

numere reale; notǎm cu numǎrul aflat la intersecția liniei i cu

coloana j, unde . Arǎtați cǎ:

.

Existǎ tablouri pentru care inegalitatea este strictǎ?

Rezolvare:

Un exemplu pentru care inegalitatea este strictǎ este

(pentru care 4 > 2)

Fie un numǎr natural și mulțimea . Cȃte dintre ecuațiile au soluțiile reale?

GM7/1988

Rezolvare: Avem de calculat numǎrul perechilor pentru care: . Pentru , inecuația are soluțiile deci are soluții.

Pentru , orice element al lui M este soluție a inecuației deci avem ȋncǎ soluții.

Numǎrul ecuațiilor care au soluții reale este:

Fie și . Demonstrați relația:

.

Rezolvare: Numǎrǎm ȋn douǎ moduri. Egalitatea poate fi o relație care transpune matematic o problemǎ de numǎrare.

Ȋntr-un oraș existǎ un grup de n suporteri. Ȋntre aceștia p țin cu prima echipǎ , q țin cu a doua echipǎ și r țin cu a treia echipǎ. Se alege un numǎr de m suporteri care sǎ reprezinte acest oraș. Ȋn cȃte moduri putem alege acest grup?

Primul mod de numǎrare : alegem m suporteri dintre cei n. Avem moduri de a face aceasta alegere.

Al doilea mod: alegem suporterii ȋn funcție de echipa pe care o susțin. Avem x suporteri dintre cei p ai primei echipe, y suporteri dintre cei q ai celei de-a doua echipe și z suporteri dintre cei r ai celei de-a treia echipe astfel ca .

Adunǎm aceste relații și obținem moduri de a alege acest grup și de aici concluzia problemei.

Pe un cerc sunt scrise 2014 numere, doi de 1 și 2012 de 0. Se poate efectua următoarea operație: se alege un număr și i se schimbă cei doi vecini din 0 ȋn 1 și invers. Făcȃnd astfel de operații, putem să obținem 2014 de 1 pe cerc?

(Andrei Eckstein, prelucrare după o problemă dată la Olimpiada Rio Plata, 1997)

Rezolvare: Ȋn funcție de poziția celor doi de 1 de pe cerc vom avea mai multe rǎspunsuri. Dacă atribuim celor 2014 numere, alternativ, douǎ culori, alb și negru, răspunsul este că dacă cele două cifre de 1 au aceeași culoare atunci nu putem face ca toate numerele de pe cerc să devină 1, ȋn vreme ce ȋn cazul ȋn care cele două cifre de 1 au culori diferite, putem ajunge la configurația finală dorită.

Dacă 1-urile au aceeași culoare: să observăm că numărul de 1-uri negre este invariant la o operație. Orice operație vizează fie două numere negre fie două numere albe. Dacă ea vizează numere negre, numărul de 1-uri negre poate să crească cu 2 (dacă se schimbă două 0-uri negre ȋn 1-uri), să scadă cu 2 (dacă se schimbă două 1-uri negre ȋn 0-uri) sau să rămȃnă neschimbat dacă se schimbă un 0 și un 1 ȋntr-un 1 și respectiv un 0. Dacă inițial 1-urile au aceeași culoare, atunci avem fie zero fie două 1-uri negre, oricum un număr par. Prin urmare numărul de 1-uri negre de pe cerc va fi mereu par. La final, ar trebui să avem numai 1-uri, ȋn particular 1007 1-uri negre, adică un număr impar. Acest lucru nu este posibil, deci nu putem ajunge la respectiva configurație.

Dacă 1-urile au culori diferite: să observăm că putem face cei doi de 1 să fie vecini.

Ȋntr-adevăr, dacă inițial ei nu sunt vecini, putem alege un 0 vecin cu un 1 și face operația. Efectul este că numǎrul 1 se va ,,muta" ȋn poziția simetrică față de 0-ul ales.

Repetȃnd această manevră, putem face ca cei doi de 1 să devină vecini. Celelalte 2012 numere le grupăm acum cȃte 4. Ȋn fiecare din cele 503 grupe, alegem, pe rȃnd, cele două cifre din mijloc și facem operația. Cele două operațiii vor transforma grupa de patru 0-uri ȋn patru de 1. Procedȃnd astfel pentru fiecare grupă, vom transforma toate numerele de pe cerc ȋn 1-uri.

Observație: Enunțul problemei date la Olimpiada Rio Plata:

Pe un cerc sunt scrise 1996 de 0 și un 1. Singura operație permisă e să alegem un număr și să-i schimbăm vecinii din 0 ȋn 1 și invers. Făcȃnd astfel de operații, putem preschimba toate numerele de pe cerc ȋn 1-uri? Dar dacă am fi pornit cu

1997 de 0 pe cerc?

Rezolvare: Dacǎ la ȋnceput avem 1996 zerouri, putem ajunge să avem numai 1-uri, iar dacă am avea 1997 zerouri, nu putem ajunge la o cofigurație doar cu 1.

Cu 1996 zerouri, putem face 499 grupe de cȃte 4, apoi facem operația alegȃnd al doilea și al treilea 0 din fiecare grup.

Cu 1997 zerouri, observăm că numărul de cifre de 0 existente pe cerc nu-și schimbă paritatea. Inițial avem un număr impar de zerouri, 1997, deci nu putem ajunge la configurația ȋn care să avem 0 zerouri (adică un număr par).

Ioana plaseazǎ jetoane pe pătrățelele unei table 8_8 astfel ȋncȃt ȋn fiecare din cele 64 de pătrățele să fie cel mult un jeton. Determinați, cu justificare, numărul maxim de jetoane pe care Ioana le poate plasa pe tablă astfel ca pe nicio linie, pe nicio coloană și pe niciuna din cele două diagonale ale tablei să nu se afle 5 sau mai multe jetoane.

Olimpiadă Marea Britanie, 2012, turul I

Rezolvare: Deoarece pe fiecare din cele 8 linii ale tablei se pot pune cel mult 4 jetoane, pe tablă se pot pune ȋn total cel mult de jetoane. Aceasta este ȋnsă doar o estimare, pentru a dovedi că numărul maxim de jetoane ce pot fi plasate pe tablă respectȃnd condițiile din enunț este ȋntr adevăr 32, mai trebuie să dăm un exemplu de un mod de amplasare a 32 de jetoane respectȃnd condițiile. Sunt multe asemenea exemple, unele mai simetrice (vezi exemplele de mai jos), altele nu. Orice exemplu valid ȋncheie rezolvarea problemei: pe de o parte am arătat că se pot pune cel mult 32 de jetoane, pe de altă parte exemplul arată că 32 de jetoane se pot plasa pe tablă, deci maximul cerut este 32.

Pe un cerc sunt plasate 2014 monede, toate cu ,,stema" ȋn sus. Sunt permise douǎ tipuri de mutǎri:

1. se pot ȋntoarce 4 monede consecutive;

2. se pot ȋntoarce 4 monede dispuse XXOXX, unde X desemneazǎ pozițiile monedelor care vor fi ȋntoarse, iar O este poziția unei monede care nu va fi mișcatǎ. Este posibil ca, dupǎ un numǎr finit de mutǎri, toate monedele sǎ fie cu ,,banul" ȋn sus?

Turneul Orașelor, 1994

Rezolvare: Vopsim monedele, alternativ, cu douǎ culori diferite, roșu și negru. Inițial, vom avea 1007 monede roșii cu ,,stema" ȋn sus. La orice mutare sunt ȋntoarse douǎ monede albastre și douǎ monede roșii. Observǎm comportamentul celor douǎ monede roșii dupǎ o mutare. Dacǎ erau douǎ cu ,,stema" ȋn sus, dupǎ mutare vor fi amȃndouǎ cu ,,banul" ȋn sus, deci numǎrul total al monedelor roșii care au ,,stema" ȋn sus va scǎdea cu 2. Dacǎ exact una dintre cele douǎ monede colorate ȋn roșu e cu ,,stema" ȋn sus, atunci și dupǎ efactuarea mutǎrii vom avea tot una din cele douǎ monede roșii cu ,,stema" ȋn sus, (aceasta este cealaltǎ monedǎ roșie care era ȋnaintea mutǎrii cu „banul” ȋn sus. Deci numǎrul total al monedelor roșii care au ,,stema" ȋn sus nu se schimbǎ. Dacǎ ȋnaintea mutǎrii, cele douǎ monede roșii pe care le mutǎm erau cu

,,banul" ȋn sus, dupǎ mutare ele vor avea ,,stema" ȋn sus, de unde numǎrul total de monede roșii care au ,,stema" ȋn sus crește cu 2. Ȋn concluzie, orice mutare am efectua, paritatea numǎrului de monede roșii care au ,,stema" ȋn sus nu se schimbǎ.

Ȋn prima fazǎ aceastǎ sumǎ era 1007, adicǎ imparǎ deci dupǎ orice mutare efectuatǎ, aceastǎ sumǎ rǎmȃne imparǎ.

Dacǎ am putea sǎ ajungem ca toate monedele (ȋn spețǎ toate monedele roșii) sǎ fie cu ,,banul"

ȋn sus, am avea suma egalǎ cu 0, adicǎ parǎ, ceea ce nu este posibil. Prin urmare nu putem face ca toate monedele sǎ fie cu ,,banul" ȋn sus.

La o competiție sportivǎ  participǎ  201 elevi din cinci unitǎț i școlare. Știind cǎ  în fiecare grup de șase elevi, cel puțin doi elevi sunt de aceeași vârstǎ , arǎtați cǎ  exist  cel puțin cinci elevi de la aceeașiunitate școlarǎ , de aceeași vârstǎ  și de același sex.

Rezolvare: Mai întâi avem cǎ din cei 201 elevi participanți, cel puțin 101 elevi de același sex: .

Dar cum în fiecare grup de șase elevi, cel puµin doi elevi au aceeași vârstǎ , deci în grupul elevilor participanµi sunt cel mult cinci vârste diferite. Ȋn grupul celor 101 elevi de același sex, avem 21 elevi de aceeași vârstǎ  ().

Dar elevii sunt din cinci unitǎți școlare diferite și printre cei 21 de elevi de același sex și cu aceeași vârstǎ, vom avea 5 elevi care provin de la aceeași școalǎ  ()

Pentru fiecre număr complex z definim mulțimea

.

Să se determine numerele complexe z pentru care este mulțime finită.

Câte numere complexe z au proprietatea că are 2013 elemente?

G.M.12/2013

Rezolvare:

, deci nu este finită, iar este finită.

Fie acum , deci este finită este finită are ordin finit în grupul deci z este rădăcină de ordin n a unității, .

Fie . Cum .

În total vom avea

Vom spune cǎ un numǎr natural este de origine klingonianǎ dacǎ ȋndeplinește simultan urmǎtoarele douǎ condiții:

Este format din 12 cifre, toate fiind nenule și mai mici sau egale cu 3;

Conține cel puțin o secvența de 11 (douǎ cifre egale cu 1).

Cȃte numere de origine klingonianǎ existǎ?

(Propusǎ de Cristinel Mortici la Concurs Sorin Sǎileanu, 2014)

Rezolvare: (Soluția propusă de autor) Cu cifrele se pot scrie numere de 12 cifre.

Notǎm: numărul numerelor de n cifre formate cu elemente din

care nu conțin vreo secvență de 11:

numărul numerelor de n cifre formate cu elemente din care nu conțin vreo secvență de 11 și au ultima cifră 1:

numărul numerelor de n cifre formate cu elemente din care nu conțin vreo secvență de 11 și au ultima cifră 2 sau 3.

Evident , și .

Cum și , efectuând calculele obținem . Vom avea

numere de origine klingoniană.

Metoda a II-a (propusǎ de elevii C.N.Ienăchiță Văcărescu)

Fie numǎrul posibilităților de a scrie șiruri de lungime i care au pe ultima poziție ( poziția i) cifra j, iar k va fi 0 dacâ numerele generate nu conțin secvența 11, iar k va fi 1 dacâ numerele generate conțin 11.

Soluția se obține pentru .

Relația de recurențâ pe care o obținem pentru și

dacă , adică pe pozițiile și nu avem valoarea 1. (secvențele posibile sunt doar 21, 22, 23, 31, 32, 33), sau

dacă (secvențele generate sunt 12, 13).

Pentru și

dacă sau

dacă .

Rămâne să calculăm acum .

Bibliografie:

Cristinel Mortici, Bazele matematicii, teorie și probleme, Editura Minus, 2007

Cristinel Mortici, Sfaturi matematice, teme și probleme, Editura Minus, 2007

Colecția Gazeta Matematicǎ

Adrian Petrușel, coordonator, Algebrǎ pentru excelențǎ, clasele IX-XII, Editura Studia, Cluj Napoca, 2010

www.viitoriolimpici.ro

Dan Schwartz, Gabriel Popa, Probleme de numǎrare, Editura GIL Zalǎu, 2007

Laurențiu Panaitopol, Dinu Șerbǎnescu, Probleme de teoria numerelor și combinatoricǎ pentru juniori, Editura GIL Zalǎu 2003

Daniela Catană și colectiv, Bacalaureat 2009, ghid , Editura Gimnazium, 2009

Bibliografie:

Cristinel Mortici, Bazele matematicii, teorie și probleme, Editura Minus, 2007

Cristinel Mortici, Sfaturi matematice, teme și probleme, Editura Minus, 2007

Colecția Gazeta Matematicǎ

Adrian Petrușel, coordonator, Algebrǎ pentru excelențǎ, clasele IX-XII, Editura Studia, Cluj Napoca, 2010

www.viitoriolimpici.ro

Dan Schwartz, Gabriel Popa, Probleme de numǎrare, Editura GIL Zalǎu, 2007

Laurențiu Panaitopol, Dinu Șerbǎnescu, Probleme de teoria numerelor și combinatoricǎ pentru juniori, Editura GIL Zalǎu 2003

Daniela Catană și colectiv, Bacalaureat 2009, ghid , Editura Gimnazium, 2009