36 1. COMBINATORICA

1.3 Principiul porumbelului

Principiul porumbelului (engl. pigeonhole principle) este o regula simpla derationament ın combinatorica existentiala:

Principiul porumbelului. Daca k + 1 sau mai multe obiecte sunt puseın k cutii atunci cel putin o cutie contine cel putin doua obiecte.

Exemplul 1. Intr-un grup de 367 persoane sunt cel putin 2 persoane cuaceeasi zi de nastere.

Demonstratie: Orice an (bisect sau nu) are cel mult k = 366 zile. Grupulare k + 1 persoane deci cel putin 2 persoane au aceeaai zi de nastere. ⇤Exemplul 2. Cati elevi trebuie sa fie ıntr-o clasa pentru a fi siguri ca celputin doi dintre ei au primit aceeasi nota? Se presupune ca notele acordatesunt de la 0 la 10.

Raspuns: Sunt k = 11 posibilitati de dat o nota. Conform principiuluiporumbelului, trebuie sa fie cel putin k+1 = 12 elevi ın clasa pentru a aveacel putin 2 elevi cu aceeasi nota. ⇤Principiul porumbelului poate fi generalizat:

Principiul generalizat al porumbelului. Daca N obiecte sunt puseın k cutii, atunci cel putin o cutie contine cel putin dN/ke obiecte.

Exemplul 3. Intr-un grup de 100 persoane sunt cel putin 9 persoanenascute ın aceeasi luna.

Demonstratie: Anul are 12 luni, deci sunt cel putin d100/12e = 9 per-soane nascute ın aceeasi luna. ⇤Exemplul 4. Cate carti trebuie luate din un pachet de 52 carti de jocpentru a fi siguri ca avem cel putin 3 carti de aceeasi culoare?

Raspuns: Presupunem ca sunt 4 cutii ın care punem cartile luate din pa-chet, cate o cutie pentru fiecare culoare de carte de joc. Conform principiu-lui generalizat al porumbelului, daca luam N carti atunci cel putin o cutiecontine dN/4e carti. Cel mai mic numar N pentru care dN/4e = 3 esteN = 9, deci trebuie luate 9 carti din pachet. ⇤Exemplul 5. Cate carti trebuie luate din un pachet de 52 carti de jocpentru a fi siguri ca avem cel putin 2 carti de culoare rosu?

Raspuns: Sunt 52/4 = 13 carti de fiecare culoare. In cel mai rau caz, niciuna din primele 3 · 13 = 39 carti selectate nu este rosu. Pentru a fi siguri ca

1.3. PRINCIPIUL PORUMBELULUI 37

avem cel putin 2 carti rosu, trebuie luate 39 + 2 = 41 carti din pachet. ⇤

1.3.1 Aplicatii remarcabile

Teorema 1. Presupunem ca m,n 2 N � {0}. O secventa cu mai multde m · n numere reale trebuie sa contina fie o subsecventa crescatoare delungime cel putin m+1, sau o subsecventa strict descrescatoare de lungimecel putin n+ 1.

Demonstratie: Fie S0 secventa respectiva si

S = r1, r2, . . . , rm·n+1

secventa primelorm·n+1 elemente ale lui S0. Pentru fiecare 1 i m·n+1,fie ai lungimea celei mai lungi subsecvente crescatoare ce ıncepe cu ri, si dilungimea celei mai lungi subsecvente strict descrescatoare ce ıncepe cu ri.

De exemplu, daca S = 3, 5, 8, 10, 6, 1, 9, 2, 7, 4 atunci

a2 = 3 (pentru subsecventa 5, 8, 10 sau 5, 8, 9)d2 = 2 (pentru subsecventa 5, 1 sau 5, 2 sau 5, 4)

Demonstram teorema prin reducere la absurd. Daca Teorema 1 ar fi falsa,am avea 1 ai m si 1 di n pentru toti i 2 {1, 2, . . . ,m · n+ 1}, decimultimea de perechi {hai, dii | 1 i m · n + 1} ar avea cel mult m · nelemente. Conform principiului porumbelului, exista 1 i < j m · n + 1cu hai, dii = haj , dji. Deducem ca (1) lungimea maxima a subsecventelorcrescatoare ce pornesc din ri si din rj este ai, si (2) lungimea maxima asubsecventelor strict descrescatoare ce pornesc din ri si din rj este di.

Acest lucru este imposibil fiindca

1. daca ri rj atunci ri lungime aiz }| {rj . . .

| {z }lungime ai+1

, ceea ce contrazice (1).

2. daca ri > rj atunci ri >

lungime diz }| {rj > . . .

| {z }lungime di+1

, ceea ce contrazice (2).

Rezulta ca Teorema 1 are loc. ⇤Inainte de a indica aplicatia urmatoare, reamintim cateva notiuni de bazadespre numere reale: daca x 2 R atunci

• bxc este cel mai mare ıntreg m 2 Z astfel ıncat m x, iar dxe este celmai mic ıntreg m 2 Z astfel ıncat x m,

38 1. COMBINATORICA

• partea fractionara a lui x este {x} = x� bxc.

• un numar irational este un numar din multimea R�Q.

Teorema urmatoare dovedeste ca numerele irationale pot fi aproximate oricatde bine cu un numar rational.

Teorema 2 (Teorema de aproximare a lui Dirichlet). Daca ↵ este unnumar irational si Q un ıntreg pozitiv, atunci exista un numar rational p/qcu 1 q Q astfel ıncat

����↵� p

q

���� 1

q · (Q+ 1). (1.18)

Demonstratie. Impartim intervalul [0, 1] ın Q + 1 subintervale disjunctede lungime 1/(Q+ 1):

I1 =

0,

1

Q+ 1

◆, I2 =

1

Q+ 1,

2

Q+ 1

◆, . . . , IQ+1 =

Q

Q+ 1, 1

�

Deasemenea, definim urmatoarele Q+ 2 numere reale:

r1 = 0, r2 = {↵}, r3 = {2↵}, . . . , rQ+1 = {Q↵}, rQ+2 = 1.

Cele Q + 2 numere sunt ın Q + 1 subintervale disjuncte, deci exista indicii1 i < j Q + 2 astfel ıncat ri, rj sunt ın acelasi subinterval, adica|ri� rj | 1/(Q+1). Se observa ca hi, ji 6= h1, Q+ 2i, pentru ca acest lucruar implica |ri � rj | = |r1 � rQ+2| = 1 > 1/(Q+ 1). Deasemenea

r1 = 0 ·↵� 0rk = (k � 1) ·↵� b(k � 1)↵c daca 2 i Q+ 1

rQ+2 = 0 ·↵� (�1)

Deci fiecare numar rk este de forma uk · ↵ + vk cu uk, vk 2 Z, si ui 6= ujfiindca hi, ji 6= h1, Q+ 2i. Rezulta ca

|ri � rj | = |(ui � uj) · ↵+ (vi � vj)| = |ui � uj || {z }q2[1,Q]

·����↵� vi � vj

ui � uj| {z }pq

���� 1

Q+ 1

deci (1.18) are loc pentru un numar rational p/q cu 1 q Q. ⇤Teorema 3. Daca n 2 N si A este o multime de n + 1 numere cuprinseıntre 1 si 2n, atunci exista a, b 2 A, a 6= b astfel ıncat a divide b.

1.3. PRINCIPIUL PORUMBELULUI 39

Demonstratie: Fie A = {a1, a2, . . . , an+1}. Fiecare numar ai se scrie ınmod unic sub forma ai = 2ki · qi cu ki, qi 2 N si qi numar impar. Rezulta caq1, q2, . . . , qn+1 sunt numere impare cuprinse ıntre 1 si 2 · n � 1. Deoareceintervalul [1, 2n � 1] contine n numere impare, exista i < j astfel ıncatqi = qj , deci ai = qi · 2ki , aj = qi · 2kj cu ki 6= kj . Fie a = min{ai, aj} sib = max{ai, aj}. Este evident ca a, b 2 A, a 6= b si a divide b. ⇤

1.3.2 Concluzii

Principiul porumbelului este un criteriu simplu si puternic de analiza ın com-binatorica existentiala, adica de determinare a existentei unor aranjamentecu anumite proprietati.

1.3.3 Exercitii

1. Intr-un grup de 6 persoane, orice pereche de indivizi sunt prieteni saudusmani. Demonstrati ca grupul respectiv contine fie 3 indivizi caresunt prieteni ıntre ei, fie 3 indivizi csre sunt dusmani ıntre ei.

2. Un sertar contine 12 ciorapi maro si 12 ciorapi negri.

(a) Cati ciorapi trebuie scosi din sertar pentru a fi siguri ca au fostscosi cel putin 2 ciorapi de aceeasi culoare?

(b) Cati ciorapi trebuie scosi din sertar pentru a fi siguri ca au fostscosi cel putin 4 ciorapi negri?

3. Cate numere trebuie selectate din multimea {1, 2, 3, 4, 5, 6} pentru a fisiguri ca am selectat cel putin 2 numere a caror suma este 7?

4. n pugilisti concureaza ıntr-un turneu care prevede un meci ıntre fie-care pereche de pugilisti. Fiecare pugilist a pierdut cel putin un meci.Demonstrati ca cel putin 2 pugilisti au obtinut acelasi numar de vic-torii.

40 1. COMBINATORICA

1.4 Principiul incluziunii si excluziunii

Principiul incluziunii si excluziunii este o generalizare a regulii sumei dinteoria numararii:

Daca A,B sunt multimi finite, atunci numarul de posibilitati de a alegeun element din A [B este |A|+ |B|� |A \B|.

Versiunea generala a principiului incluziunii si excluziunii este

Daca A1, A2, . . . , An sunt multimi finite atunci numarul de posibilitatide a alege un element din

Sni=1Ai este

|A1 [A2 [ . . . [An| = |A1 + |A2|+ . . .+ |An|� |A1 \A2|� |A1 \A3|� . . . (toate perechile)

+ |A1 \A2 \A3|+ . . . (toate triplurile)

. . .

+ (�1)n�1|A1 \A2 \ . . . \An|.

Exercitiul 1. Un sertar contine 50 margele: 25 sunt de sticla, 30 sunt rosii,20 sunt sferice, 18 sunt de sticla rosie, 12 sunt sferice de sticla, 15 sunt sfericerosii, si 8 sunt sferice de sticla rosie. Cate margele exista care nu sunt nicirosii, nici de sticla si nici sferice?

Raspuns: Fie multimea A1 a margelelor de sticla, A2 a margelelor rosii,si A3 a margelelor sferice. Numarul cautat este 50 � |A1 [ A2 [ A3|. Dindatele problemei stim ca |A1| = 25, |A2| = 30, |A3| = 20, |A1 \ A2| = 18,|A1 \A3| = 12, |A2 \A3| = 15 si |A1 \A2 \A3| = 8. Deasemenea, stim ca

|A1 [A2 [A3| = |A1|+ |A2|+ |A3|� |A1 \A2|� |A1 \A3|� |A2 \A3|+ |A1 \A2 \A3| = 25 + 30 + 20� 18� 12� 15 + 8 = 38

deci numarul cautat este 50� 38� 12. ⇤Exercitiul 2⇤. Ce arie are octogonul gri din figura de mai jos?

A B

P

M

O

N

CD

1.4. PRINCIPIUL INCLUZIUNII SI EXCLUZIUNII 41

Se presupune ca ABCD este un patrat cu latura 1 si ca M,N,O, P suntmijloacele laturilor AB,BC,CD,DA.

Raspuns: Fie {Fi | 1 i 8} multimea triunghiurilor echilaterale {ABP ,ABN,BCO,BCM,CDP,CDN,DAM,DAO}, si S octogonul gri din fi-gura. In cele ce urmeaza vom folosi notatia a(F ) pentru aria unei figurigeometrice F . Ni se cere sa calculam a(S).

Se observa usor ca a(Fi) = 1/4 pentru 1 i 8, si

a(S) = a(ABCD)� a

8[

i=1

Fi

!= 1� a

8[

i=1

Fi

!.

Conform principiului generalizat al incluziunii si excluziunii, avem

a

8[

i=1

Fi

!=

8X

i=1

a(Fi)�X

1i<j8

a(Fi \ Fj) +X

1i<j<k8

a(Fi \ Fj \ Fk)

= 2�X

1i<j8

a(Fi \ Fj) +X

1i<j<k8

a(Fi \ Fj \ Fk).

Doua figuri diferite Fi, Fj se pot suprapune ın trei feluri, indicate prin zonelegri ın figurile de mai jos:

S1

S2 S3

iar trei figuri diferite Fi, Fj , Fk se pot suprapune ın un singur fel:

S1

Rezulta ca

X

1i<j8

a(Fi \ Fj) +X

1i<j<k8

a(Fi \ Fj \ Fk) = 4 · (a(S2) + a(S3)).

Insa a(S2) = a(F1)/2 = 1/8. Deasemenea, din figura de mai jos

42 1. COMBINATORICA

S3

A B

G

M

P

D

rezulta ca |PB| =p

|AB|2 + |AP |2 =p5/2 si

• G este centrul de greutate al lui ABD, deci |PG| = |PB|3 =

p56

• distanta de la A la PB este d(A,PB) = |AP |·|AB||PB| = 1p

5.

Prin urmare a(S3) = 2 · a(APG) = |PG| · d(A,PB) = 16 . Asadar

4 · (a(S2) + a(S3)) = 4 ·✓1

8+

1

6

◆=

7

6

si a(S) = 2� 7

6=

5

6. ⇤

Inainte de a ilustra exercitiul urmator, reamintim cate notiuni si proprietatielementare din teoria numerelor.

I Doua numere a, b 2 N sunt prime ıntre ele daca cel mai mare divizorcomun al lor este 1: gcd(a, b) = 1. De exemplu, 5 si 2 sunt prime ıntreele fiindca gcd(5, 12) = 1.

I Daca a, b,m 2 N si gcd(a, b) = 1 atuncim este multiplu de a si multiplude b daca si numai daca este multiplu de a · b.

I Daca A,B, d 2 N, A B si d > 0 atunci intervalul [A,B] contineB �A+ 1 numere ıntregi, dintre care bBd c � dAd e+ 1 se divid cu d.

Exercitiul 3. Cate numere ıntregi cuprinse ıntre 50 si 213 sunt divizibilecu 5 sau 12?

Raspuns: Fie A multimea ıntregilor din intervalul [50, 213] divizibili cu 5,si B multimea ıntregilor din intervalul [50, 213] divizibili cu 12. Avem decalculat |A[B|. gcd(5, 12) = 1, deci A\B este multimea ıntregilor divizibilicu 5 · 12 = 60.

A \BA B

multiplide 5 · 12

multiplide 5

multiplide 12

1.4. PRINCIPIUL INCLUZIUNII SI EXCLUZIUNII 43

Conform principiului incluziunii si excluziunii: |A[B| = |A|+ |B|� |A\B|.Deasemenea, stim ca

|A| =�213

5

⌫�⇠50

5

⌫+ 1 = 42� 10 + 1 = 33,

|B| =�213

12

⌫�⇠50

12

⌫+ 1 = 17� 5 + 1 = 13,

|A \B| =�213

60

⌫�⇠50

60

⌫+ 1 = 3� 1 + 1 = 3

deci numarul cautat este 33 + 13� 3 = 43. ⇤Exercitiul 4. O parola este un sir de 7 caractere ASCII care contine olitera mare si o cifra zecimala. Se stie ca multimea de caractere ASCII are128 caractere dintre care 26 sunt litere mari iar 10 sunt cifre zecimale. Cateastfel de parole se pot forma?

Raspuns: Fie A multimea caracterelor ASCII, S multimea parolelor posi-bile si S0 multimea sirurilor de 7 caractere ASCII. Ni se cere sa calculam|S|. Se observa ca S ✓ S0. Deci, conform regulii sumei: |S0| = |S|+ |S0�S|.Rezulta ca |S| = |S0|� |S0 � S| = 1287 � |S0 � S|.

Pe de alta parte, S0 � S = X [ Y unde X este multimea sirurilor de7 caractere ASCII ın care nu apare nici o litera mare, iar Y este multimeasirurilor de 7 caractere ASCII ın care nu apare nici o cifra zecimala. Conformprincipiului incluziunii si excluziunii

|S0 � S| = |X [ Y | = |X|+ |Y |� |X \ Y |= (128� 26)7 + (128� 10)7 � (128� 26� 10)7

= 1027 + 1187 � 927.

Deci numarul de parole posibile este 1287 � 1027 � 1187 + 927. ⇤

1.4.1 O notatie convenabila

In general, daca A este o multime finita iar P1, P2, . . . , Pn sunt proprietatipentru elementele din A, vom folosi notatia Ai pentru multimea de elementedin A cu proprietatea Pi, N(Pi1Pi2 . . . Pik) pentru numarul de elemente dinA care au proprietatile Pi1 , Pi2 , . . . , Pik , si N(P 0

i1P0i2 . . . P

0ik) pentru numarul

de elemente din A care nu au nici una din proprietatile Pi1 , Pi2 , . . . , Pik . Deci

N(Pi1Pi2 . . . Pik) = |Ai1 \Ai2 \ . . . \Aik |,N(P 0

i1P0i2 . . . P

0ik) = |A|� |Ai1 [Ai2 [ . . . [Aik |

44 1. COMBINATORICA

iar din principiul incluziunii si excluziunii rezulta ca

N(P 01P

02 . . . P

0n) = |A|�

nX

i=1

N(Pi) +X

ii1<i2n

N(Pi1Pi2)

�X

ii1<i2<i3n

N(Pi1Pi2Pi3) + . . .+ (�1)nN(P1P2 . . . Pn).

Exercitiul 5. Cate solutii are ecuatia

x1 + x2 + x3 = 11

daca x1, x2, x3 2 N, x1 3, x2 4 si x5 6?

Raspuns: Fie A = {hx1, x2, x3i 2 N3 | x1 + x2 + x3 = 11}, si proprietatileurmatoare: P1 daca x1 > 3, P2 daca x2 > 4, si P3 daca x3 > 6. Ni se ceresa calculam N(P 0

1P02P

03).

N(P 01P

02P

03) = |A|�N(P1)�N(P2)�N(P3)

+N(P1P2) +N(P1P3) +N(P2P3)�N(P1P2P3).

Insa |A| = C(3 + 11� 1, 3� 1) = 78 (vezi Exercitiul 21 de la pagina 14) si

• hx1, x2, x3i 2 A1 este echivalent cu x1 = 4+ u si hu, x2, x3i 2 N3 astfelıncat u+ x2 + x3 = 11� 4 = 7, deci N(P1) =

�7+3�13�1

�=�92

�= 36,

• hx1, x2, x3i 2 A2 este echivalent cu x2 = 5+ u si hx1, u, x3i 2 N3 astfelıncat x1 + u+ x3 = 11� 5 = 7, deci N(P2) =

�6+3�13�1

�=�82

�= 28,

• hx1, x2, x3i 2 A3 este echivalent cu x3 = 7+ u si hx1, x2, ui 2 N3 astfelıncat x1 + x2 + u = 11� 7 = 4, deci N(P1) =

�4+3�13�1

�=�62

�= 15,

• hx1, x2, x3i 2 A1 \ A2 este echivalent cu x1 = 4 + u, x2 = 5 + vsi hu, v, x3i 2 N3 astfel ıncat u + v + x3 = 11 � 4 � 5 = 2, deciN(P1P2) =

�2+3�13�1

�=�42

�= 6,

• hx1, x2, x3i 2 A1 \ A3 este echivalent cu x1 = 4 + u, x3 = 7 + vsi hu, x2, vi 2 N3 astfel ıncat u + x2 + v = 11 � 4 � 7 = 0, deciN(P1P3) =

�0+3�13�1

�=�20

�= 1,

• hx1, x2, x3i 2 A2 \ A3 este echivalent cu x2 = 5 + u, x3 = 7 + v sihx1, u, vi 2 N3 astfel ıncat x1 + u+ v = 11� 5� 7 = �1. Deoarece nuexista un astfel de tuplu, N(P1P2) = 0,

1.4. PRINCIPIUL INCLUZIUNII SI EXCLUZIUNII 45

• hx1, x2, x3i 2 A1 \ A2 \ A3 este echivalent cu x1 = 4 + u, x2 = 5 + v,x3 = 7+w, si hu, v, wi 2 N3 astfel ıncat u+v+w = 11�4�5�7 = �5.Deoarece nu exista un astfel de tuplu, N(P1P2P3) = 0.

Rezulta ca N(P 01P

02P

03) = 78� 36� 28� 15 + 6 + 1 + 0� 0 = 6. ⇤

Exercitiul 6⇤⇤. La o conferinta de presa participa 200 jurnalisti vorbitoride germana, franceza, engleza si japoneza, dintre care: 175 vorbesc germana,150 vorbesc franceza, 180 vorbesc engleza, si 160 vorbesc japoneza. Careeste numarul minim de jurnalisti participanti la conferinta care vorbesc toatecele patru limbi?

Raspuns: Fie A multimea celor 200 de jurnalisti, si P1, P2, P3, P4 calitatilelor de a putea vorbi germana, franceza, engleza si japoneza. Fie

x = N(P1P2P3P4),

y1 = N(P 01P2P3P4), y2 = N(P1P

02P3P4),

y3 = N(P1P2P03P4), y4 = N(P1P2P3P

04),

z12 = N(P 01P

02P3P4), z13 = N(P 0

1P2P03P4), z14 = N(P 0

1P2P3P04),

z23 = N(P1P02P

03P4), z24 = N(P1P

02P3P

04), z34 = N(P1P2P

03P

04),

u1 = N(P1P02P

03P

04), u2 = N(P 0

1P2P03P

04),

u3 = N(P 01P

02P3P

04), u4 = N(P 0

1P02P

03P4).

A diagrama Venn a intersectiilor multimilor Ai este ilustrata mai jos:

x y2 z23

y1z13

u1

u2

z14

z12

z34 y4

y3

z24

u3

u4

unde A1

z34

y3

y4

x

z24

y2 z23

u1

A3

y4 z24

x y2

y1 z12

z14 u3

A2

z34 y4

y3 x

z13 y1

z14

u2

A4

y3

z13

x

y1

y2

z12

z23

u4

Observatie: o diagrama Venn pentru 4 multimi nu se poate desena cu cer-curi, dar se poate desena cu dreptunghiuri.

Ni se cere sa aflam valoarea minima a lui x ın prezenta constrangerilor

|A| = x+3X

i=1

(yi + ui) + z12 + z13 + z14 + z23 + z24 + z34 = 200,

|A1| = N(P1) = x+ y2 + y3 + y4 + z23 + z24 + z34 + u1 = 175,

46 1. COMBINATORICA

|A2| = N(P2) = x+ y1 + y3 + y4 + z13 + z14 + z34 + u2 = 150,

|A3| = N(P3) = x+ y1 + y2 + y4 + z12 + z14 + z24 + u3 = 180,

|A4| = N(P4) = x+ y1 + y2 + y3 + z12 + z13 + z23 + u4 = 160,

x, y1, y2, y3, u1, u2, u3, z12 + z13 + z14, z23 + z24 + z34 2 N.

Aceasta este o problema de programare liniara cu ıntreagi (engl. integerlinear programming), care este dificila.1. In schimb, aflarea valorii minime alui x 2 R ın prezenta constrangerilor

x+4X

i=1

(yi + ui) + z12 + z13 + z14 + z23 + z24 + z34 = 200,

x+ y2 + y3 + y4 + z23 + z24 + z34 + u1 = 175,

x+ y1 + y3 + y4 + z13 + z14 + z34 + u2 = 150,

x+ y1 + y2 + y4 + z12 + z14 + z24 + u3 = 180,

x+ y1 + y2 + y3 + z12 + z13 + z23 + u4 = 160,

x, y1, y2, y3, u1, u2, u3, z12 + z13 + z14, z23 + z24 + z34 � 0

este o problema de programare liniara care se poate rezolva usor cu algo-ritmul simplex. Algoritmul simplex este implementat ın numeroase sistemesoftware de calcul. In Mathematica [13], poate fi apelat cu comanda

care confirma ca minimul este atins cand x = 65, y1 = 25, y2 = 50, y3 = 20,y4 = 40, z12 = z13 = z14 = z23 = z24 = z34 = 0. Deoarece aceste valorisunt numere naturale, rezulta ca numarul minim posibil de jurnalisti carevorbesc toate cele patru limbi este x = 65. ⇤

1Se stie programarea liniara cu ıntregi este o problema NP-completa.

1.4. PRINCIPIUL INCLUZIUNII SI EXCLUZIUNII 47

1.4.2 Aplicatii remarcabile

Functia totient

In 1763, Euler a definit functia ' : N � {0} ! N, unde '(n) este numarulıntregilor 1 m < n cu gcd(m,n) = 1. De exemplu, '(24) = 8 fiindca sunt8 ıntregi 1 m < n cu gcd(m, 24) = 1: 1.5,7,11,13,17,19,23.

' se numeste functia totient a lui Euler. Aceasta functie joaca un rolimportant ın teoria numerelor.

In cele ce urmeaza vom descoperi o formula simpla de calcul al lui '(n)cu ajutorul principiului generalizat al incluziunii si excluziunii.

Fie n = pn11 · . . . · pnr

r descompunerea unica a lui n ın produs de puteride numere prime distincte, cu ni > 0 pentru 1 i r, si A multimeanumerelor 1 m < n cu gcd(m,n) = 1. Pentru fiecare 1 i r definimmultimea Ai = {m 2 N | 1 m n si pi divide n}. Se observa usor caA =

Sri=1Ai. Conform principiului incluziunii si excluziunii

'(n) = n� |A| = n�

�����

r[

i=1

Ai

�����

= n�rX

i=1

|Ai|+X

1i1<i2r

|Ai1 \Ai2 |� . . .+ (�1)n|A1 \ . . . \Ar|.

Deoarece numerele p1, . . . , pr sunt prime ıntre ele, rezulta ca daca 1 k rsi 1 i1 < i2 < . . . < ik r atunci multimea Ai1 \ . . . \ Aik continetoate numerele 1 m pn1

1 · . . . · pnrr divizibile cu pi1 · . . . · pik . Elementele

acestei multimi sunt numerele u · pi1 · . . . · pik cu 1 u npi1 ·...·pik

, deci

|Ai1 \Ai2 \ . . . \Aik | = npi1pi2 ·...·pik

de unde rezulta ca

'(n) = n�rX

i=1

n

pi+

X

1i1<i2r

n

pi1pi2+ . . .+ (�1)r

n

p1 . . . pr

= n ·rY

i=1

✓1� 1

pi

◆.

De exemplu, numarul de ıntregi strict pozitivi m < 24 cu gcd(m,n) = 1 este

'(24) = '(23 · 31) = 24 ·✓1� 1

2

◆·✓1� 1

3

◆= 24 · 1

2· 23= 8.

48 1. COMBINATORICA

Numararea numerelor prime

Ne punem problema numararii numerelor prime mai mici sau egale ca n,unde n 2 N. Daca n nu este prim atunci n = a · n cu a, b 2 N si 1 < a b,ceea ce implica a2 n, deci a

pn. Altfel spus, n trebuie sa fie divizibil cu

un numar prim p pn. Rezulta criteriul urmator de numarare a numerelor

prime mai mici sau egale ca n:

Fie N = {1, 2, . . . , n} si n0 numarul de elemente ramase dupa ce eli-mina din N multiplii de numere prime p

pn. n0 nu este numarul

cautat fiindca (1) nu am numarat numerele prime mai mici sau egaleca n, si (1) am numarat 1. Deci numarul cautat este n0 � r + 1 under este numarul numerelor prime mai mici sau egale ca

pn.

Exercitiul 6. Cate numere prime sunt mai mici sau egale ca 120?

Raspuns: Multimea numerelor prime p p120 este {2, 3, 5, 7}, deci numarul

cautat este n0 � 4 + 1 = n0 + 3 unde

n0 = {n 2 N | 1 n 120} si n nu este multiplu de 2,3,5,7}= 120� {n 2 N | 1 n 120} si n este multiplu de 2,3,5 sau 7}= 120� |A2 [A3 [A5 [A7|

unde Ap = {n 2 N | 1 n 120 si n este multiplu de p}. Conform princi-piului generalizat al incluziunii si excluziunii, avem ca

|A2 [A3 [A5 [A7| = |A2|+ |A3|+ |A5|+ |A7|� |A2 \A3|� |A2 \A5|� |A2 \A7|� |A3 \A5|� |A3 \A7|� |A5 \A7|+ |A2 \A3 \A5|+ |A2 \A3 \A7|+ |A2 \A5 \A7|+ |A3 \A5 \A7|� |A2 \A3 \A5 \A7|

= |A2|+ |A3|+ |A5|+ |A7|� |A6|� |A10|� |A14|� |A15|� |A21|� |A35|+ |A30|+ |A42|+ |A70|+ |A105|� |A210|

= 60 + 40 + 24 + 17� (20 + 12 + 8 + 8 + 5 + 3)

+ (4 + 2 + 1 + 1)� 0 = 141� 56 + 8 = 93

deci numarul cautat este (120� 93) + 3 = 30. ⇤

1.4. PRINCIPIUL INCLUZIUNII SI EXCLUZIUNII 49

1.4.3 Concluzii

Principiul incluziunii si excluziunii este un criteriu simplu si puternic denumarare ın combinatorica enumerativa, care generalizeaza regula sumei:

• Daca A,B sunt doua multimi finite atunci

|A [B| = |A|+ |B|� |A [B|.

• In general, daca A1, A2, . . . , An sunt multimi finite atunci

|A1 [A2 [ . . . [An| = |A1 + |A2|+ . . .+ |An|� |A1 \A2|� |A1 \A3|� . . . (toate perechile)

+ |A1 \A2 \A3|+ . . . (toate triplurile)

. . .

+ (�1)n�1|A1 \A2 \ . . . \An|.

1.4.4 Exercitii

1. Cate siruri de 7 biti ıncep cu 00 sau se termina cu 000?

2. Cate numere ıntregi cuprinse ıntre 50 si 1500 inclusiv

(a) se divid cu 3?

(b) se divid cu 7?

(c) se divid cu 7 dar nu se divid cu 3?

(d) se divid cu 3 sau cu 7?

(e) nu se divid nici cu 3 si nici cu 7?

3. Cate numere ıntregi de la 1 la 999 inclusiv

(a) se divid cu 7?

(b) se divid cu 7 si nu se divid cu 11?

(c) se divid cu 7 si 11?

(d) se divid cu 7 sau 11?

(e) se divid cu doar unul din numerele 7, 11?

(f) au cifre distincte?

(g) sunt pare si au cifre distincte?

4. Cate numere prime sunt mai mici sau egale ca 101?

50 1. COMBINATORICA

5. Intr-o clasa sunt 14 fete si 16 baieti. Stim ca 22 persoane din clasarespectiva sunt blonde. Care este numarul minim de fete blonde dinclasa respectiva?

6. Se considera multimea celor 50 de steaguri ale SUA. Stim ca

• 30 steaguri au fundal albastru,

• 12 steaguri au dungi,

• pe 26 steaguri apare o planta sau un animal,

• 9 steaguri au fundal albastru si dungi,

• 23 steaguri au fundal albastru si o planta sau animal,

• 3 steaguri au dungi si o planta sau animal,

• un singur steag (California) are dungi si o planta sau animal, darnu are fundal albastru.

Cate state din SUA au steaguri fara fundal albastru, fara dungi, sifara planta sau animal?

7. Cate submultimi ale multimii {a, b, c, d, e, 1, 2, 3, 4} contin cel putin olitera si cel putin o cifra?