S iruri si sub siruri n analiza matematic a [612631]

S iruri  si sub siruri ^ n analiza matematic a
Scarlat Maria Andreea Roxana

2

Cuprins
1 Teoria  sirurilor 5
1.1 S iruri de numere reale. Denit ie  si propriet at i . . . . . . . . . . . 5
1.2 Not iunea de convergent  a . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Criterii suciente de convergent  a sau de existent  a a limitei unui  sir 8
1.4 Calcularea limitelor de  siruri tip . . . . . . . . . . . . . . . . . . 10
1.5 S iruri remarcabile . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 S irul lui Fibonacci . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 S irul lui Traian Lalescu . . . . . . . . . . . . . . . . . . . 12
1.5.3 Constanta lui Euler . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 S irul lui Newton . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Criterii de convergent  a ale  sirurilor . . . . . . . . . . . . . . . . . 13
1.6.1 Criteriul de convergent  a cu ". . . . . . . . . . . . . . . . 13
2 Teoria sub sirurilor 15
2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Aplicat ii ale teoriei  sirurilor  si sub sirurilor ^ n analiza matem-
atic a 17
3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Aplicat ii alese din concursurile  scolare  si olimpiade ale teoriei
 sirurilor  si sub sirurilor 19
4.1 Grafurile neorientate  si aplicat ii ^ n matematica de gimnaziu  si liceu 20
4.2 Lant uri . Cicluri . Grafuri conexe . Aplicat ii ^ n matematica de
gimnaziu  si liceu . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3

4 CUPRINS

Capitolul 1
Teoria  sirurilor
1.1 S iruri de numere reale. Denit ie  si pro-
priet at i
Prin sirse ^ nt elege o innitate de numere, distincte sau, nu, scrise unul dup a
altul.
Exemplul 1.1. S irul numerelor naturale: 1, 2, 3, 4, … .
Denit ia 1.2. Numim  sir de numere reale orice funct ie f:N!R,f(n) =
an.
Not am (an)n>0.
Exemplul 1.3. 1. 1, 1, 1, 1, . . . 1, . . .
2. 1, -1, 2, -2, . . . , n, -n, . . .
3. 10, 102,103,104, . . . , 10n, . . .
4. 1,1
2,1
3,1
4,. . .1
n, . . .
5. 1,1
2,1
3,1
4,. . .(1)n+1
n, . . .
Metode de denire a unui  sir de numere reale
Deoarece  sirul este o funct ie, modalit at ile de a deni un  sir sunt generate de
cele ale denirii unei funct ii:
1.S iruri denite descriptiv
^In acest sens se d a primul termen  si c^ at iva din termenii urm atori, astfel
^ nc^ at s a se observe o regul a de obt inere a oric arui termen al  sirului.
Exemplul 1.4. 1;3;5;7;9;


, regula este scrierea numerelor naturale
impare. Deci an= 2n+ 1,n2N.
Exemplul 1.5. 1;3;32;33;


, regula este scrierea puterilor naturale ale
lui3. Decian= 3n,n2N.
Exemplul 1.6. 1;1
2;1
3;1
4;


, regula este scrierea inverselor numerelor
naturale. Deci an=1
n,n2N.
5

6 CAPITOLUL 1. TEORIA S IRURILOR
2.S iruri denite cu ajutorul unei formule (analitic)
Denirea prin formul a a unui  sir ^ nseamn a exprimarea termenului gen-
eral printr-o anumit a expresie. Expresia care determin a ecare termen
al  sirului (an)n2Nfolosind rangul s au nse nume ste formula termenului
generalan.
Exemplul 1.7. an=n2+ 1
Obt inema1= 12+ 1;a2= 22+ 1;a3= 32+ 1etc.
Exemplul 1.8. an=n+1
n2+1. Astfel, pentru n=1, n=2, n=3, etc. Se obt ine
 sirul (an)1+1
12+1,2+1
22+1,3+1
32+1,



Observat ie 1.9. Termenul general al unui  sir poate  exprimat  si prin
mai multe formule.
Exemplul 1.10. Fie  sirul (an)n2Nal c arui termen general este dat prin
an=
n+ 1; pentru n impar
2n; pentru n par
Obt inema1= 1 + 1 = 2 ,a2= 2
2 = 4 ,a3= 3 + 1 = 4 ,a4= 4
2 = 8 etc.
3.S iruri denite recurent
Relat ia de recurent  a este formula cu ajutorulu c areia se exprim aorice ter-
men al  sirului, ^ ncep^ and de la un anumit rang, ^ n funct ie de unul sau de
mai mult i din termenii precedent i.
Exemplul 1.11. Fie  sirul (an)n2Ndenit prin: a1= 2;an+1=1
3an,
n1.
Cunosc^ and primul termen al  sirului a1= 2 si leg atura dintre termenul de
rangn+ 1 si termenul de rang n, dat a prin formula an+1=1
3an,n1,
putem g asi oricare termen al  sirului dup a cum urmeaz a:
a1= 2
a2=1
3a1=1
3
2 =2
3
a3=1
3a2=1
3
2
3=2
32etc.
Exemplul 1.12. Fie  sirul (an)n2Ndenit prin: a1= 1;a2=2;
an+2=an+13an,n1.
Cunosc^ and primul  si al doilea termen al  sirului a1= 2,a2=2 si leg atura
dintre termenii de rang n+ 1,n+ 2 si termenul de rang n, dat a prin for-
mulaan+2=an+13an,n1, putem g asi oricare termen al  sirului dup a
cum urmeaz a:
a1= 2
a2=2
a3=a23
a1=23
1 =5
a4=a33
a2=53
(2) = 1 etc.
Denit ia 1.13. S irul (an)n>0este m arginit dac a exist a M > 0astfel ^ nc^ at
janjM, pentru orice n2N.
Exemplul 1.14. S irulan= cosneste m arginit, deoarece termenii s ai sunt
mai mari sau egali cu 1 si mi mici sau egali cu 1.

1.2. NOT  IUNEA DE CONVERGENT  A 7
Denit ia 1.15. S irul (an)n>0este monoton cresc ator dac a anan+1. S irul
(an)n>0este monoton descrec ator dac a anan+1.
Exemplul 1.16. S irul000;1;2;3;


;n;


00este cresc ator;001;1
2;1
3;1
4;


;1
n;


;00
este descresc ator.
Denit ia 1.17. S irul (an)n>0este m arginit dac a  si numai dac a 9M > 0astfel
^ nc^ atjanjM,8n2N.
Notat ie (an)n>0,an2R,R=R[f1;+1g.
Denit ia 1.18. S irul (an)n>0,an2Rare limitaa si scriem
lim
n!1an=a
,a2Rdac a ^ n orice vecin atate a punctului ase a
 a toti termenii  sirului
^ ncep^ and de la un anumit rang.
Denit ia 1.19. S irul este convergent,
lim
n!1an=a
,a2R, dac a8">0,9N"2Nastfel ^ nc^ at8n>N ",janaj<"
Denit ia 1.20.
lim
n!1an= +1
, dac a8">0,9N"2Nastfel ^ nc^ at an>",8n>N ".
Denit ia 1.21.
lim
n!1an=1
, dac a8">0,9N"2Nastfel ^ nc^ at an<",8n>N ".
Dac a
lim
n!1an=1
,atunci  sirul este divergent.
1.2 Not iunea de convergent  a
Dac a observ am c a termenii  sirului ( an)n>0se apropie din ce ^ n ce mai mult
de num arul a(se"^ ngr am adesc"), pe m asur a ce ncre ste, vom avea o viziune
intuitiv a asupra convergent ei  sirului. Vom spune c a an!a(antinde, converge
c atre a),aind limita  sirului.
Vom nota
lim
n!1an=a
. Mai exact:
Denit ia 1.22. S irul (an)n>0este convergent c atre asau are limita adac a
orice vecin atate a lui a(interval deschis care-l cont ine pe a) cont ine tot i termenii
 sirului, except^ and (eventual) un num ar nit de termeni.

8 CAPITOLUL 1. TEORIA S IRURILOR
Sau:
Denit ia 1.23. S irul (an)n>0este convergent c atre a(are limita a) dac a
8" > 0,9n">0(un rang depinz^ and de "), astfel ^ nc^ at8nn"s a avem
janaj<".
Observat ie 1.24. Limita unui  sir, dac a exist a, este unic a.
Teorema 1.25. Orice  sir monoton  si m arginit este convergent.
Exemplul 1.26. S irulan= (1
2)nse constat a u sor c a este descresc ator: 1>
1
2>1
4>


>1
2
n>


 si m arginit inferior de 1; deci limn!11
2
n= 1.
Propriet at i ale  sirurilor convergente:
limita modulului este egal a cu modulul limitei;
limita sumei (diferent ei, produsului, c^ atului-dac a exist a) este egal a cu
suma (diferent a, produsul, c^ atul) limitelor;
constanta iese ^ n fat a limitei;
limita radicalului este egal a cu radicalul limitei;
limita unei puteri se distribuie bazei  si exponentului, adic a lim ( xy) =(limx)limy;
limita logaritmului este egal a cu logaritmul limitei; etc.
Aspectele prezentate mai sus, aprofundate pe baz a de exemple, vor constitui
baza calcului limitelor de  siruri.
Exemplul 1.27. Fie  sirul cu termenul general an=1!+2!+


+n!
(2n)!. S a se calculeze
limn!1an.
Solut ie 1.28. Aveman<n
n!
(2n)!=n
(n+1)(n+2)


(2n)=)an<1
n+2,8n2.
Cum limn!11
n+2= 0 =)limn!1an= 0.
1.3 Criterii suciente de convergent  a sau de existent  a
a limitei unui  sir
1. dac a lim n!1bn= 0,bn0  sijanajbnatunci lim n!1an=a;
2. dac a lim n!1bn=1 sianbnatunci lim n!1an=1;
3. dac a lim n!1bn=1  sianbnatunci lim n!1an=1;
4. orice  sir monton  si m arginit este convergent (criteriul lui Weierstrass);
5. dac abnancn si lim n!1bn= lim n!1cn=aatunci lim n!1an=a;
6. criteriul lui Stolz
dac a (bn)n0cresc ator: lim n!1bn=1 si exist a lim n!1an+1an
bn+1bn, atunci
limn!1an
bn= lim n!1an+1an
bn+1bn;

1.3. CRITERII SUFICIENTE DE CONVERGENT  A SAU DE EXISTENT  A A LIMITEI UNUI S IR 9
dac a (an)n0,an>0  si exist a lim n!1an+1
anatunci lim n!1npan= lim n!1an+1
an.
(Cesaro);
dac a (bn)n0cresc ator: lim n!1an= lim n!1bn= 0  si exist a lim n!1an+1an
bn+1bn,
atunci lim n!1an
bn= lim n!1an+1an
bn+1bn;
Operat ii cu  siruri care au limit a
Teorema 1.29. 1. Dac a limn!1an=a,a2R silimn!1bn=b,b2R,
atunci limn!1(an+bn) =a+b= lim n!1an+ lim n!1bn.
2. Dac a limn!1an=a;a2R si2R, atunci limn!1(an) =an=
limn!1an;
3. Dac a limn!1an=a,a2R silimn!1bn=b,b2R, atunci limn!1(anbn) =
ab= lim n!1anlimn!1bn.
4. Dac a limn!1an=a,a2R silimn!1bn=b,b2R,b6= 0  sibn6= 0,
8n2N, atunci lim
n!1an
bn=a
b=lim
n!1an
lim
n!1bn.
5. Dac a lim
n!1an=a>0, undean>0,8n2N silim
n!1bn=b2R, atunci
lim
n!1abnn=ab=
lim
n!1anlim
n!1bn
6. Dac a lim
n!1an=a silim
n!1bn=b, undean>0,an6= 1,bn>0,8n2N,
a>0,a6= 0,b>0, atunci lim
n!1
loganbn

=logab=loglim
n!1an
lim
n!1bn

10 CAPITOLUL 1. TEORIA S IRURILOR
Tabelul 1.1: OPERAT  II ^INR, NEDETERMIN ARI
Tipul de operat ii Operat ii care au sens Nedetermin ari
a+1=1+a=1
a1 =1+a=1 11 ;1+1
Adun ari, sc aderi 1+1=1 (tipul11 )
11 =1
a
1=1
a=1, dac aa>0 0
1;1
0; 0
(1); (1)
0
^Inmult iri, ^ mp art iri a
1=1
a=1, dac aa<0 (tipul1
0)
a
(1) = (1)
a=1, dac aa>01
1;1
1;1
1;1
1
a
(1) = (1)
a=1, dac aa<0 (tipul1
1)
1
1 =10
0
1
(1) = (1)
1=1
(1)
(1) =1
a
1= 0
a
1= 0
a1= 0, dac a1<a< 1 11; 11
a1=1, dac aa>1 (tipul 11)
Puteri a1= 0, dac aa>1 10
01= 0 00
1a=1, dac aa>0
1a= 0, dac aa<0
11=1
11= 0
1.4 Calcularea limitelor de  siruri tip
1.
lim
n!1qn=8
>><
>>:0; dac a1<q< 1
1; dac aq= 1
+1; dac aq>1
nu exist a; dac aq1
2.
lim
n!1
a0nk+a1nk1+


+ak1n+ak

= lim
n!1a0nk=+1; dac aa0>0
1; dac aa0<0
3.
lim
n!1a0nk+a1nk1+


+ak1n+ak
b0np+b1np1+


+bp1n+bp=8
>><
>>:0; dac ak<p
+1; dac ak>p  sia0b0>0
1; dac ak>p  sia0b0<0
a0
b0; dac ak=p
4. lim
n!1
1 +q+q2+


+qn

=1
1q, dac ajqj<1;
5. lim
n!1
1 +1
2+1
3+


+1
n

= +1;

1.5. S IRURI REMARCABILE 11
6. lim
n!1npa= 1,8p1;
7. lim
n!1np1p+ 2p+


+np= 1,8p1;
8. lim
n!1
1 +1
n
n=e;
9. lim
n!1
1 +1
1!+1
2!+
+1
n!
n=e.
1.5 S iruri remarcabile
1.5.1 S irul lui Fibonacci
S irul lui Fibonacci , (Fn)n1este denit de recurent a: F1= 1,F2= 1,
Fn=Fn1+Fn2, pentrun3.
Termenul general se scrie : Fn=1p
5h
1+p
5
2n

1p
5
2ni
Proof. Pentru demonstrarea termenului general al  sirului lui Fibonacci vom uti-
liza metoda induct iei matematice.
Not am cuP(n) :Fn=1p
5h
1+p
5
2n

1p
5
2ni
, pentrun3.
Etapa 1
Veric am valoarea de adev ar pentru n= 1
P(1):F1=1p
5h
1+p
5
2

1p
5
2i
=1p
5h
1+p
51+p
5
2i
=1
2p
5
2p
5 = 1, adev arat.
Etapa 2
Presupunem c a P(k) adev arat a  si demonstr am c a P(k+ 1) este adev arat a,
pentru8k2N.
P(k) :Fk=1p
5
1+p
5
2k

1p
5
2k
, pentru8k2N,  si relat ia de
recurent  a:
8
<
:F1= 1;
F2= 1;
Fk=Fk1+Fk2; k2N,k3
P(k+ 1) :Fk+1=1p
5
1+p
5
2k+1

1p
5
2k+1
, pentru8k2N.
Conform relat iei de recurent  a avem:
F(k+1) =F(k)+F(k1) =1p
5
1+p
5
2k

1p
5
2k
1p
5
1+p
5
2k1

1p
5
2k1
=1p
5
(1+p
5)k
2k+(1+p
5)k1
2k1(1p
5)k
2k(1p
5)k1
2k1
=1p
5
(1+p
5)k1(1+p
5+2)
2k(1p
5)k1(1p
5+2)
2k
=1p
5
(1+p
5)k1(3+p
5)
2k(1p
5)k1(3p
5)
2k
=1p
5
(1+p
5)k1
2k
(1+p
5)2
2(1p
5)k1
2k
(1p
5)2
2
=1p
5h
(1+p
5)k+1
2k+1(1p
5)k+1
2k+1i
=1p
5
1+p
5
2k+1

1p
5
2k+1
,8k2N=)
P(k+ 1) adev arat a.
Propozit iaP(k+ 1) este adev arat a pentru 8k2N=)induct ie matematic a
=)P(n) adev arat a.

12 CAPITOLUL 1. TEORIA S IRURILOR
1.5.2 S irul lui Traian Lalescu
S irul lui Traian Lalescu este denit prin termenul s au general: Ln=
n+1p
(n+ 1)!np
n!,n2, av^ and lim
n!1Ln=1
e.
Proof. Pentru demonstrarea  sirului lui Traian Lalescu vom folosi urm atoarea
propozit ie:
Propozit ia 1.30. Fie(an)n1un  sir de numere strict pozitive care veric a
urm atoarele condit ii:
1.lim
n!1an+1
an= 1;
2.lim
n!1an
n=2(0;1);
3.lim
n!1
an+1
ann
=2R.
Prin urmare lim
n!1(an+1an) =ln
Vom nota cu an=np
n!,n2.
Aplic^ and a doua condit ie din popozit ia de mai sus obt inem:
lim
n!1an
n= lim
n!1np
n!
n= lim
n!1nq
n!
nn
Not am cuxn=n!
nn
xn+1
xn=(n+1)!
(n+1)n+1
n!
nn=(n+1)!
(n+1)n+1
nn
n!=n!(n+1)
(n+1)n+1
nn
n!=nn
(n+1)n
A sadar, aplic^ and prima condit ie din propozit ia de mai sus obt inem: lim
n!1xn+1
xn=
lim
n!1
n
n+1n
= lim
n!1
n+11
n+1n
= lim
n!1
1 +1
n+1(n+1)1
n+1
n
=e1=1
e
lim
n!1an+1
an= lim
n!1n
np
n!
n+1p
(n+1)
n+1
n+1
n=1
e
e
1 = 1
Aplic^ and ultima condit ie, avem:
lim
n!1
an+1
ann
= lim
n!1
n+1p
(n+1)!
np
n!n
= lim
n!1
n+1
np
n!n
n+1=e
Prin urmare, : lim
n!1Ln= lim
n!1
n+1p
(n+ 1)!np
n!
=1
e
lne=1
e
1.5.3 Constanta lui Euler
S irul cu termenul general
cn= 1 +1
2+1
3+


+1
nlnn;n1
este strcit descresc ator  si minorant de 0; limita sa
= lim
n!1cneste numit a
constanta lui Euler (
= 0;577:::); exist a inegalitatea
1
2n+ 1<cn
<1
2n:

1.6. CRITERII DE CONVERGENT  A ALE S IRURILOR 13
1.5.4 S irul lui Newton
S irul lui Newton este denit prin recurent a:
an+1=1
p
(p1)an+a
ap1
n
;n1;a> 0;p2N;p2:
Avem proprietatea:
lim
n!1an=ppa:
1.6 Criterii de convergent  a ale  sirurilor
1.6.1 Criteriul de convergent  a cu "
Teorema 1.31. Fie(an)n1un  sir de numere reale. Atunci:
i.lim
n!1an=l2R() 8" > 0;9n"2Nastfel ^ nc^ at8nn"=)
janlj<".
ii.lim
n!1an= +1 () 8">0;9n"2Nastfel ^ nc^ at8nn"=)an>".
iii.lim
n!1an=1 () 8 " >0;9n"2Nastfel ^ nc^ at8nn"=)an<
".
Proof. i.00)00Presupunem c a lim
n!1an=l, ^ nsemn^ and c a orice vecin atate
a luilcont ine tot i termenii de la un rang ^ ncolo.
A sadar, pentru8" >0, vecin atatea ( l";l+")2V(l) cont ine tot i ter-
menii  sirului ^ ncep^ and de la un anumit rang, adic a 9n"2Nastfel ^ nc^ at
8nn"=)an2(l";l+"), prin urmare l" < a n< l+"()
"<a nl<"() janlj<".
00(00
Presupunem c a pentru 8">0;9n"2Nastfel ^ nc^ at8nn"=) jan
lj< ": FieV2V(l) o vecin atate oarecare a lui l=) 9" > 0 astfel
^ nc^ at (l";l+")VConform ipotezei, 9n"=nV2Nastfel ^ nc^ at
8nnV=) janlj< "()an2(l";l+")()an2V()
lim
n!1an=l.
ii.00)00Presupunem c a lim
n!1an= +1, ^ nsemn^ and c a orice vecin atate a
lui +1cont ine tot i termenii  sirului de la un rang ^ ncolo. A sadar, pentru
8" >0, vecin atatea ( ";1]2Vcont ine tot i termenii  sirului ^ ncep^ and de
la un anumit rang , adic a 9n"2Nastfel ^ nc^ at8nn"=)an2
(";1]()an>".
00(00
Presupunem c a8" > 0;9n"2Nastfel ^ nc^ at8n > n "=)an> ".
FieV2V(1) o vecin atate arbitrar a a lui 1=) 9" >0 astfel ^ nc^ at
(";1]VConform ipotezei, 9n"=nV2Nastfel ^ nc^ at8nnV=)
an>"=)an2(";1]()an2V() lim
n!1an= +1.

14 CAPITOLUL 1. TEORIA S IRURILOR
ii.00)00Presupunem c a lim
n!1an=1, ^ nsemn^ and c a orice vecin atate a
lui +1cont ine tot i termenii  sirului de la un rang ^ ncolo. A sadar, pentru
8" > 0, vecin atatea [1;")2Vcont ine tot i termenii  sirului ^ ncep^ and
de la un anumit rang , adic a 9n"2Nastfel ^ nc^ at8nn"=)an2
[1;")()an<".
00(00
Presupunem c a8">0;9n"2Nastfel ^ nc^ at8n>n "=)an<". Fie
V2V(1) o vecin atate arbitrar a a lui 1 =) 9" >0 astfel ^ nc^ at
[1;")VConform ipotezei, 9n"=nV2Nastfel ^ nc^ at8nnV=)
an<"=)an2[1;")()an2V() lim
n!1an=1.

Capitolul 2
Teoria sub sirurilor
2.1
2.2
2.3
15

16 CAPITOLUL 2. TEORIA SUBS IRURILOR

Capitolul 3
Aplicat ii ale teoriei  sirurilor
 si sub sirurilor ^ n analiza
matematic a
3.1
17

18CAPITOLUL 3. APLICAT II ALE TEORIEI S IRURILOR S I SUBS IRURILOR ^IN ANALIZA MATEMATIC A

Capitolul 4
Aplicat ii alese din
concursurile  scolare  si
olimpiade ale teoriei
 sirurilor  si sub sirurilor
Acum mai bine de 500 de ani italianul Paulo Guarini di Forli a propus un puzzle
care a r amas celebru.
Aplicat ia 4.1. ^In colt urile unei table de  sah 3 x 3 se a
 a patru cai , doi albi
si doi negri ( gura 1a). este posibil ca, ^ ntr-un num ar nit de mut ari, s a
schimb am pozit iile cailor albi cu cele ale cailor negri (gura 1b) ? Dac a da ,
care este num arul minim de mut ari necesare ?
Dac a nu avem la dispozit ie o tabl a de  sah , putem ^ ncerca s a desen am o dia-
gram a (gura 1c)^ n care marc am ecare c^ amp al tablei cu un punct, numerot am
aceste puncte de la 1 la 9  si unim cu c^ ate un segment punctele corespunz atoare
unei mut ari posibile. Totu si , analiza nu pare a  simpl a . Vrem, de exemplu ,
s a mut am calul negru din pozit ia 1 ^ n pozit ia 7 sau 9. S a ^ ncerc am 7 : mut am
mai ^ nt^ ai 1 ^ n 6 ,  si apoi ^ n 7, dar 7 e ocupat de calul alb , a sa c a mut am mai
^ nt^ ai calul alb din 7 ^ n 2 , etc. Ideea rezolv arii este observat ia c a , ^ n diagrama
desenat a , nu pozit ia absolut a a punctelor  si segmetelor conteaz a , ci pozit ia lor
relativ a . Cu alte cuvinte, putem a seza cele 9 puncte oricum ^ n plan , av^ and
^ ns a grij a ca segmetele s a uneasc a acelea si perechi de puncte. Astfel, putem
obt ine diagrama din gura 1d , pe care observam foarte clar cum se pot mi sca
piesele. Nu e greu de v azut c a , pentru a schimba locurile cailor, ecare cal
trebuie s a execute minim 4 mut ari, deci e nevoie de cel put in 16 mut ari ^ n total.
^In nal , calul de pe pozit ia 1 va  pepozit ia 9, 3 pe 7 , 9 pe 1  si 7 pe 3 S a
mai examin am un exemplu . Este vorba de o problem a propus a la vestitul con-
curs pentru student ii universit at ilor de top din Statele Unite  si Canada, ,,W.L.
Putnam Mathematical Competition" , ^ n anul 1953. Ast azi , aceast a problem a
poate  g asit a, sub diverse formul ari , ^ n majoritatea culegerilor de probleme
pentru gimnaziu .
Aplicat ia 4.2. ^Intr-un grup de  sase persoane , unele se cunosc reciproc , altele
19

20CAPITOLUL 4. APLICAT II ALESE DIN CONCURSURILE S COLARE S I OLIMPIADE ALE TEORIEI S IRURILOR S I SUBS IRURILOR
nu . S a se arate c a exist a trei persoane dintre cele  sase care se cunosc ecare
cu ecare, sau exist a trei persoane dou a nu se cunosc .
S i ^ n acest caz o diagram a ne poate  de ajutor. S a reprezent am cele  sase
persoane prin  sase puncte ^ n plan  si s a unim ecare pereche de puncte printr-un
segment linie continu a dac a persoanele corespunz atoare se cunosc , respectin
linie puncat a dac a nu se cunosc. Este clar c a avem de dovedit existent auni
triunghi cu laturile acela si fel (linie continu a sau punctat a)1.^In gura 2a avem
un exemplu de diagram a posibil a , ^ n care triunghiuri monocromatice sunt BDF
siCDF . S a examin am segmentele care au un cap at ^ n punctul A . Sunt 5 la
num ar , ecare ind desenat e cu linie continu a, e cu linie punctat a. ^In mod
sigur , cel put in 3 dintre cele 5 segmente vor  desenate cu acela si tip de linie.
S a presupunem , f ar a a restr^ ange generalitatea , c a avem 3 segmente desenate
cu linie continu a , de exemplu AC , AD  si AF (gura 2b). Dac a vreunul dintre
segmentele CD , DF sau CF este desenat tot cu linie continu a , atunci formeaz a
un triunghi monocromatic . Dac a toate cele 3 segmente sunt punctate , atunci
se formeaz a triunghiul monocromatic CDF ( gura 2c) . Astfel problema estere
zolvat a.
Observat ii
1) Num arul 6 este num arul minim cu proprietatea din problem a . ^In gura
2d avem o diagram a corespunz atoare unei mult imi de 5 persoane , ^ n care nu
exist a triunghiuri monocromatice .
2) Consider^ and 18 puncte ^ n spat iu unite dou a c^ ate dou a cu segmente col-
orate cu 2 culori , se poate ar ata c a exist a 4 puncte , printre cele 18 , care
formeaz a un tetraedru ale c ariu muchii sunt colorate cu aceea si culoare .
Propunem cititorului interesat dou a probleme legate de enunt ul precedent .
Aplicat ia 4.3. Ar att i c a , ^ n condit iile problemei 2 exist a cel put in dou a tri-
unghiuri monocromatice .
Aplicat ia 4.4. Se consider a 6puncte ^ n spat iu , astfel ^ nc^ at distant a dintre
cele dou a c^ ate dou a distincte . Aceste puncte determin a6
2

= 15 segmente  si6
3

= 20 de triunghiuri . S a se arate c a exist a un segment care este ^ n acela si
timp latura cea mai mic a a unui triunghi  si latura cea mai mare a altui triunghi.
4.1 Grafurile neorientate  si aplicat ii ^ n matem-
atica de gimnaziu  si liceu
Diagramele pe care le-am folosit ^ n rezolvarea problemelor precedente reprezint a
ceea ce ^ n matematic a numim grafuri . Intuitiv , un graf este format dintr-o
mult ime de puncte ( numite v^ arfuri ), unele dintre ele ind unite , segemente
sau arce ( numite muchii). ^In cele ce urmeaz a , ne vom referi numai la grafuri
simple  si nite , aceasta ^ nsemn^ and c a num arul v^ arfurilor este nit oricare dou a
v^ arfuri sunt unite de cel mult o muchie  si nici un v^ arf nu este unit printr-o
muchie cu el ^ nsu si .
Astfel , putem deni un graf ca ind o pereche G= (V;M ) , unde V este
o mult ime nit a , iar M este o mult ime format a din submult imi cu elemente
1Numim un astfel de triunghi monocromatic

4.1. GRAFURILE NEORIENTATE S I APLICAT II ^IN MATEMATICA DE GIMNAZIU S I LICEU 21
ale lui V . Faptul c a un graf poate  reprezentat printr-un desen este un sprijin
intuitiv important . De exemplu , pentru graful din gura 3a , avem
V=fA;B;C;D;Eg,M=ffA;Bg;fA;Cg;fB;Dg;fB;Eg;fD;Egg
Este important de ret inut c a importante ^ n reprezentarea unui graf nu sunt
pozit iile punctelor ^ n plan , dac a muchiile sunt desenate ca segmente sau arce
etc.
Important este s a  stim ce pereche de v^ arfuri conecteaz a ecare muchie .
Astfel , e posibil ca acela si graf s a poat a  reprezentat de desene diferite .
Numim reprezent arile respective izomorfe ( observat i desnele din gurile 3b  si
3c , sau cele din gurile 1c  si 1d) .
Ideea folosirii unui graf ne poate ajuta s a intuim mai bine esent a unei prob-
leme . Iat a un posibil exemplu .
Aplicat ia 4.5. Din mult imeaf1;2;3;::::;99gtrebuie alese 50de numere , astfel
^ nc^ at suma oric aror dou a s a nu e egal a nici cu 99, nici cu 100.^In c^ ate moduri
se poate face alegerea ?
(Sankt Petersburg , 1996)
R aspuns. ^Intr-un singur mod . Numerele alese trebuie s a e 50, 51, ….,99 .
S a consider am un graf ^ n care v^ arfurile sunt numerele 1, 2, 3 , …… , 99. Unim
dou a v^ arfuri cu o muchie dac a  si numai dac a suma acestora este 99 sau 100.
Obt inem astfel graful din gura 4.
Constat am c a numerele din mult ime s-au ^ mp art it ^ n mod natural ^ n dou a
submult imi A=f1;2;::::;49g siB=f50;51;:::;99g, iar ecare muchie a grafu-
lui une ste un v^ arf din Acu unul din B2. Mai mult , observ am c a dac a printre
cele 50 de numere alese se a
 a k1 numere din mult imea A, atunci
cel put ink+ 1 numere din mult imea Bnu mai pot  alese ( kv^ arfuri din A
sunt conectate ^ n graful nostru cu cel put in k+ 1 v^ arfuri din B). Dar atunci ,
num arul total de numere alese este cel mult k+ (50k1) = 49 . Concluzia
este c a nu putem alege nici un num ar din mult imea A, a sadar cele 50 de numere
trebuie s a e 50 , 51 , … , 99.
O denit ie important a este aceea de grad al unui v^ arf. S a consider am un
grafG= (V;M ) si ev2V. Spunem c a v^ arful vare gradul k,  si scriem
aceastad(v) =k, dac a exist a exact kmuchii ale grafului adiacente v^ arfului v.
De exemplu , pentru gracul din gura 3a , avem d(A) =d(D) =d(E) = 2
,d(B) = 3 ,d(C) = 1 . Pentru graful din gura 1d avem d(5) = 0.
Simpla folosire a not iunii de grad poate  util a ^ n rezolvarea unor probleme
, dup a cum arat a exemplul urm ator.
Aplicat ia 4.6. ^In c asut ele unui tablou 1010se scriu cifrele 0,1, ….. ecare
cifr a ind folosit a de 10ori . S a se arate c a exist a cel put in o linie sau o coloan a
a tabloului unde apar cel put in 4cifre diferite . (Turneul Oras elor , 1993)
Vom considera un graf , tot bipartit , ale c arui v^ arfuri reprezint a reuniunea
a dou a mult imi disjuncte . Pe de o parte , mult imea Aa celor 10 cifre iar pe de
alt a parte , mult imea Ba celor 20 de linii  si coloane ale tabloului . O muchie
une ste un v^ arf din Acu unul din Bdac a cifra reprezentat a de v^ arful din Ase
reg ase ste ^ n tabloul dat ^ n linia sau coloana reprezentat a de v^ arful din B.
2Un astfel de graf se nume ste bipartit

22CAPITOLUL 4. APLICAT II ALESE DIN CONCURSURILE S COLARE S I OLIMPIADE ALE TEORIEI S IRURILOR S I SUBS IRURILOR
De exemplu, dac a ^ n prima linie a tabloului toate cele 10 c asut e cont in cifra
3 , siaeste v^ arful din Acorespunz ator acestei cifre , atunci d(a) = 2 deoarece
o muchie une ste acu v^ arful corespunz ator liniei 1, iar alte 10 muchii unesc acu
cele 10 v^ arfuri corespunz atoare celor 10 coloane (c aci ,evident ^ n ecare coloan a
se g ase ste c^ ate o cifr a 3).
S a consider am un v^ arf vdinA si s a presupunem c a cifra corespunz atoare
acestuia apare ^ n mlinii  sincoloane ale tabloului , unde , evident m;n1.
Atunci , desigur , cele 10 aparit ii ale cifrei se a
 a ^ n c asut e a
ate la intersect ia
dintre cele mlinii  si cele ncoloane , a sadar mn10. Cumm sinsunt
numere naturale nenule , deducem c a m+n7 , deci d(v)7.
Aceast a inegalitate este vericat a de ecare v^ arf din A, prin urmare are cel
put in 70 de muchii ,  si , deoarece 70 >60, conform principiului cutiei , va exista
un v^ arf ^ nBadiacent la cel put in 4 muchii. Cu alte cuvinte exist a o linie sau o
coloan a unde g asim cel put in 4 cifre diferite.
O problem a clasic a , legat a de not iunea de grad al unui v^ arf este urm atoarea.
Aplicat ia 4.7. La o petrecere la care particip a mai multe persoane , uneledintre
ele se cunosc reciproc , altele nu . S a se arate c a num arul celor care se cunosc
cu un num ar impar de persoane este par .
(Concursul E otvos ,Ungaria 1998)
^In mod natural , vom considera un graf ^ n care v^ arfurile sunt persoane ,
iar dou a v^ arfuri sunt unite cu o muchie dac a  si numai dac a persoanele core-
spunz atoare se cunosc . S a numim par un v^ arf de grad par  si impar un v^ arf de
grad impar . Astfel , trebuie s a ar at am c a num arul v^ arfurilor impare este par .
Aceasta va rezulta imediat din teorema urm atoare .
Teorema 4.8. ^In orice graf G(V;M )avem
P
v2Vd(v) = 2jMj,
unde prinjMjam notat num arul de elemente ale mult imii M, adic a num arul
de muchii ale grafului .
Demonstrat ia este simpl a . Deoarece gradul unui v^ arf este egal cu num arul
de muchii adiacente acelui v^ arf , dac a adun am toate gradele v^ arfurilor, vom
obt ine dublul num arului de muchii ale grafului, deoarece ecare muchie une ste
dou a v^ arfuri .
Revenind la problema 7 , trebuie doar s a observ am c a suma gradelor v^ arfurilor
pare este evident par a, deci , suma tuturor gradelor ind tot par a , rezult a c a
suma v^ arfurilor impare este  si ea par a . Dar suma mai multor numere impare
este par a doar dac a num arul acestora este par , ceea ce trebuia demonstrat.
Aplicat ia 4.9. La o petrecere la care particip a un num ar par de persoane , unele
dintre ele se cunosc reciproc, altele nu . S a se arate c a exist a dou a persoane
care au un num ar par de cuno stint e comune .
(Sankt Petersburg , 1995)
Faptul c a exist a dou a persoane av^ and acela si num ar de cuno stint e ( par sau
impar) este o aplicat ie binecunoscut a a principiului cutiei. Dac a num arul de
persoane participante la petrecere este n, ecare poate avea 0 ;1;2;:::;n1

4.1. GRAFURILE NEORIENTATE S I APLICAT II ^IN MATEMATICA DE GIMNAZIU S I LICEU 23
cuno stint e.Dar e clar c a , dac a o persoan a are n1 cuno stint e ( adic a per-
soana respectiv a cunoa ste toat a lumea ), nu mai poate exista o persoan a cu
0 cuno stint e. Astfel , sunt npersoane  si n1 cazuri posibile referitoare la
num arul de cuno stint e. Concluzia e evident a.
Revenind la problem a, vom rat iona prin reducere la absurd, presupun^ and c a
oricare dou a persoane au un num ar impar de cuno stint e comune. Vom ar ata mai
^ nt^ ai c a, ^ n aceast a ipotez a, oricare persoan a are un num ar par de cuno stint e.
FieAuna dintre persoane. Vom ^ mp art i restul persoanelor ^ n dou a mult imi
disjuncte: mult imea CAa cuno stint elor lui A si mult imea NA, a celor care
nu cunosc persoana A. FieB2CA; atunciA siBau un num ar impar de
cuno stint e comune care, desigur, apart in mult imii CA. CumBa fost ales
arbitrar , deducem c a orice persoan a din CAare un num ar impar de cuno stint e
^ n mult imea CA. Din problema precedent a deducem c a CAare un num ar par
de elemente , deci am ar atat ca A(  si, deci, orice alt participant la petrecere)
are un num ar par de cuno stin te.
Fie acumC2NA; la fel ,A siCau un num ar impar de cuno stint e comune.
Toate acestea apart in mult imii CA. Dar num arul total de cuno stint e ale per-
soaneiCeste par , deci Care ^ n mult imea NCun num ar impar de cuno stint e
. La fel ca mai sus , deducem c a mult imea NAare un num ar par de elemente.
Dar atunci , mult imea tuturor participant ilor la petrecere , este fAgSCAS
NAare un num ar impar de elemente , contradict ie.
Aplicat ia 4.10. Cei20de membri ai unui club de tenis au programat un mini-
turneu ^ n care se vor juca 14meciuri de simplu , astfel ^ nc^ at ecare membru
s a joace cel put in o dat a. S a se arate c a ^ n cadrul acestei program ari exist a o
submult ime de 6meciuri la care particip a 12juc atori diferit i.
(Olimpiada SUA , 1900)
Avem un graf cu 20 de v^ arfuri  si 14 muchi i. S a not am cu viv^ arful
(i=1,2,…,20). Desigur, d(vi)1 pentru orice i, c aci ecare membru joac a
cel put in o dat a.
Teorema 1 ne spune c a d1+d2+:::+d20= 28 .
Pentru ecare v^ arf vi stergemdi1 muchii adiacente acestuia( unele muchii
din graf ar putea   sterse de 2 ori), astfel , ^ n noul graf , ecare are gradul cel
mult egal cu 1.
Asta ^ nseamn a c a  stergem ^ n total cel mult
d11 +d21 +:::+d201 = 8
muchii. R am^ an a sadar cel put in 6 muchii , iar cele 12 v^ arfuri adiacente
acestora au toate gradul 1 . Am g asit astfel cei 12 juc atori diferit i care joac a
partide din turneu.
Aplicat ia 4.11. Exist a 9segmente ^ n plan astfel ^ nc^ at ecare din ele s a in-
tersecteze exact alte trei segmente , punctele de intersect ie nu sunt neap arat
distincte? ( ^In gurile 5a  si 5b sunt desenate dou a variante pentru 8segmente.)
(Mathematical…….)
Vom considera un graf ^ n care v^ arfurile vor  cele 9 segmente , o muchie va
uni 2 v^ arfuri dac a segmentele corespunz atoare se intersecteaz a. De exemplu ,
desenului din gura 5a ^ i corespunde graful din gura 5c.

24CAPITOLUL 4. APLICAT II ALESE DIN CONCURSURILE S COLARE S I OLIMPIADE ALE TEORIEI S IRURILOR S I SUBS IRURILOR
Dac a ecare segment dintre cele 9 intersecteaz a exact alte 3 segmente atunci
^ n graful nostru toate cele 9 v^ arfuri vor avea gradul 3, deci suma gradelor ar
un num ar impar , ceea ce contrazice teorema precedent a.
Propunem cititorului urm atoarele trei probleme, legate de not iunea grad.
Aplicat ia 4.12. S a se arate c a nu exist a un graf ^ n care gradele v^ arfurilor s a
e
a)4;4;4;3; b)1;1;1;2;3;5;6;6;7;9;
Aplicat ia 4.13. ^Intr-o t ar a sunt 2000 de ora se  si niciun drum. S a se arate
c a se poate construi o ret ea de drumuri astfel c a din dou a ora se s a plece c^ ate
un drum, din alte dou a, ^ cate dou a drumuri,…, din ultimile dou a, c^ ate 1000 de
drumuri.
(Sankt Petersburg , 2001)
Aplicat ia 4.14. Vlad a observat c a printre cei 25de colegi ai lui de clas a nu
exist a doi care s a aib a acela si num ar de prieteni (^ n clasa respectiv a) . Mai
mult , ecare coleg are , ^ n clas a , cel put in un prieten. C^ at i prieteni are ^ n
clas a Vlad?
(Turneul Oras elor , 1993)
4.2 Lant uri . Cicluri . Grafuri conexe . Aplicat ii
^ n matematica de gimnaziu  si liceu
S a consider am un graf G(V;M ) . Un  sir de v^ arfuri a1;a2;:::;a nale grafului astfel
^ nc^ at oricare dou a v^ arfuri consecutive sunt legate printr-o muchie , se nume ste
lant . Num arul de muchii astfel folosite se nume ste lungimea lant ului . Dac a
muchiile din lant  sunt distincte , lant ul se nume ste simplu . Dac a v^ arfurile din
lant  sunt distincte, lanc tul se nume ste elementar .
Lant ul simplu a1;a2;:::;a n^ n carea1=anse nume ste ciclu . Dac aa1;a2;:::;a n
este un lant  elementar , atunci a1;a2;:::;a n,a1se nume ste elementar .
De exemplu , ^ n graful din gura 6a, A;B;G;A;B;H;C;E este un lant ,
G;A;B;G;F;E este un lant  simplu, iar A;B;H;C;E;F este un lant  elementar.
Pe de alt a parte, A;B;H;C;E;F;A  siC;D;E;C sunt cicluri elementare.
Dac a oricare dou a v^ arfuri ale unui graf pot  unite printr-un lant  , atunci
graful se nume ste conex. Graful din gura 6a este conex, ^ n timp ce graful
din gura 6b nu este. Putem observa ^ ns a,la acest ultim graf , faptul c a el
este, de fapt, o reuniune a dou a grafuri conexe. ^In general, orice graf este o
reuniune de grafuri conexe, numite componentele conexe ale grafului init ial.
Considerarea componentelor conexe ale unui graf este un instrument util ^ n
rezolvarea problemelor. Iat a c^ ateva exemple.
Aplicat ia 4.15. Fiecare ora s al unei t  ari este legat de alte ora se printr-un
num ar par de drumuri, astfel ^ nc^ at din orice ora s se poate ajunge ^ n oricare alt
ora s (tranzit^ and eventual c^ ateva ora se). Unul dintre drumuri este ^ nchis pentru
reparat ii. S a se arate c a, ^ n continuare , din orice ora s se poate ajunge ^ n oricare
alt ora s.
Avem un graf ^ n care ecare v^ arf are grad par. Faptul c a ,,din orice ora s se
poate ajunge ^ n oricare alt ora s (tranzit^ and eventual c^ ateva ora se)" ^ nseamn a,

4.2. LANT  URI . CICLURI . GRAFURI CONEXE . APLICAT  II ^IN MATEMATICA DE GIMNAZIU S I LICEU 25
desigur, c a graful este conex. Trebuie s a ar at am c a, dac a este eliminat a o muchie
a grafului , acesta r am^ ane conex.
S a presupunem c a am eliminat muchia AB. Dac a nu putem ajunge din A
^ nB, ^ nseamn a c a v^ arfurile A siBse a
 a ^ n componente conexe diferite ale
grafului r amas dup a eliminare. Dar dac a privim doar la componenta conex a ^ n
care se a
 a A, observ am c a toate v^ arfurile din aceasta au graf par, cu except ia
luiA, care, dup a eliminarea muchiei AB,a devenit un v^ arf de grad impar.
Aceasta ^ ns a contrazice teorema 1.
Observat ie. O solut ie alternativ a folose ste urm atoarea idee: un graf ^ n care
ecare v^ arf are graf par se poate scrie ca o reuniune de cicluri elementare dis-
juncte3.^Indemn am cititorul s a demonstreze aceast a armat ie  si s a o foloseasc a
pentru a rezolva problema.
Aplicat ia 4.16. ^Intr-un grup de persoane , unele se cunosc reciproc , altele
nu.^In ecare sear a,una dintre persoane organizeaz a o petrecere , la care invit a
toate persoanele pe care le cunoa ste ,  si, celor care nu se cunosc ^ nc a, le face
cuno stint  a.
S a presupunem c a, dupa ce ecare dintre persoane a organizat cel put in o
petrecere , mai exist a dou a persoane care nu se cunosc ^ ntre ele. S a se arate c a
nici la urm atoarea petrecere nu vor face cuno stint a una cu cealalt a.
(Sankt Petersburg , 19::)
^Incepem, desigur, prin a considera graful ^ n care v^ arfurile sunt persoanele,
iar o muchie une ste dou a v^ arfuri dac a persoanele respective se cunosc reciproc.
Dup a, ecare petrecere , acest graf se mai imbog at e ste cu c^ ateva muchii. Fie
Auna dintre persoane. Deoarece la petrecerea pe care o organizeaz a particip a
doar cuno stint ele lui A, rezult a c a la aceast a petrecere particip a doar persoane
din aceea si component a conex a cu A. Deducem c a dou a persoane pot face
cuno stint  a numai dac a apart in aceleia si componente conexe a grafului.
FieB siCcele dou a persoane care nu se cunosc ^ ntre ele. Dac a nu apart in
aceleia si componente conexe a grafului , exist a un lant  care le une ste. S a con-
sider am un lant  elementar de lungime minima cu aceast a proprietate  si e n
lungimea acestuia.
Dac aAeste un v^ arf din acest lant  ( vezi gura 7a ) atunci la petrecerea pe
care o va organiza , persoana Ale va face cuno stint  a persoanelor A0 siA00(vezi
gura 7b) , astfel c a, dup a aceast a petrecere , lant ul minimal ce leag a B siC
va avea lungimea cel mult n1 . Deducem c a, dup a ce ecare dintre persoane
a organizat cel put in o petrecere , B siCar trebui s a se cunoasc a. ^Intruc^ at
nu se cunosc, ^ nseamn a c a ele apart in unor componente conexe diferite, si ,prin
urmare, nu vor face niciodat a cuno stint  a.
Aplicat ia 4.17. ^Intr-o t ar a sunt mai mult de 101 ora se. Capitala t  arii este
legat a prin linii aerieni de 100 de ora se, iar ecare ora s (cu except ia capi-
talei) este legat tot prin linii aeriene de 10alte ora se (toate liniile aeriene sunt
bidirect ionale) . Se  stie c a din orice ora s se poate ajunge ^ n oricare alt ora s
(tranzit^ and eventual c^ ateva ora se).
S a se arate c a se pot ^ nchide jum atate din liniile aeriene prin care este legat a
capitala de celelalte oras e astfel ^ nc^ at, ^ n continuare , din orice ora s s a se poat a
ajunge ^ n oricare alt ora s.
3Teorema lui Veblen (1912)

26CAPITOLUL 4. APLICAT II ALESE DIN CONCURSURILE S COLARE S I OLIMPIADE ALE TEORIEI S IRURILOR S I SUBS IRURILOR
(Turneul Oras elor , 198:)
Graful standard G, ^ n care v^ arfurile sunt ora sele, iar muchiile-liniile aeriene
este, desigur,conex. S a elimin am temporar din graf v^ arful C, care corespunde
capitalei , precum  si cele 100 de muchii incidente acestuia. Noul graf, G0, nu
mai e neap arat conex. Mai mult, ^ n noul graf, 100 de v^ arfuri au gradul 9 , iar
toate celelalte , gradul 10.
FieAun v^ arf av^ and gradul 9. Este clar c a ^ n componenta conex a ^ n care
se a
 a acesta se mai g ase ste cel put in ^ nc a un v^ arf cu gradul 9 , astfel s-ar
contrazice teorema 1. Deducem c a num arul de componente conexe ale lui G0
este cel mult 50. Revenind la graful init ial, observ am c a putem elimina (cel
put in) 50 de muchii care pleac a din C, l as^ and c^ ate o muchie care leag a Cde
ecare dintre componentele conexe ale grafului G0.
Vom examina ^ n continuare, av^ and ^ n vedere important a conceptului, c^ ateva
condit ii suciente  si condit ii necesare pentru ca un graf s a e conex. Urm atoarele
dou a probleme prezint a condit ii suciente pentru conexitate.
Aplicat ia 4.18. FieGun graf cunv^ arfuri, cu proprietatea d(v)n1
2pentru
orice v^ arfv. S a se arate c a Geste conex.
S a presupunem contrariul. Atunci Gcont ine cel put in dou a componente
conexe ,G1 siG2. Fiev2G1; atuncid(v)n1
2, deciG1are cel put in
n+1
2v^ arfuri. Similar,  si G2are cel put inn+1
2v^ arfuri. Dar atunci  si Gar avea
mininn+1
2+n+1
2=n+ 1 v^ arfuri, contradict ie.
Aplicat ia 4.19. FieGun graf cun3v^ arfuri  simmuchii , cu proprietatea
m>n1
2

. S a se arate c a Geste conex.
Vom demonstra proprietatea prin induct ie dup a n. Cazuln= 3 ind
evident, s a o presupunem adev arat a prin orice graf cu nv^ arfuri  si s a consider am
un graf cun+ 1 v^ arfuri, ^ n care num arul de muchii este mai mare dec^ atn
2

.
FieAunul dintre v^ arfuri. Evident, d(A)n.
Dac ad(A) =n, atunciAeste adiacent tuturor celorlalte v^ arfuri ale grafului
, deci graful este conex. Dac a d(A)n1 , s a elimin am v^ arful Aprecum  si
toate muchiile din A. Num arul de v^ arfuri ale noului graf este n, iar num arul
de muchii este mai mare dec^ at
n
2

(n1) =n1
2

,
a sadar putem aplica ipoteza de induct ie noului graf. Acesta va  conex ,  si,
pun^ and la loc v^ arful A si muchiile eliminate , deducem c a  si graful init ial a fost
conex.
O condit ie necesar a pentru conexitatea unui graf este dat a de urm atoarea
teorem a.
Teorema 4.20. FieGun graf cu n3v^ arfuri  simmuchii . Dac a Geste
conex, atunci mn1.
Vom demonstra amat ia prin induct ie dup a num arul de v^ arfuri . Pentru
n= 2 amat ia e evident a. S a presupunem armat ia adev arat a pentru orice
graf cunv^ arfuri,  si s a consider am un graf cu n+ 1 v^ arfuri . Vrem s a ar at am
c a el are cel put in nmuchii.
FieAv^ arful de grad minim . Dac a , d(A) = 1 , atunci Aeste legat pe o
singur a muchie de un alt v^ arf Bal grafului . Elimin^ and v^ arful A si muchia

4.2. LANT  URI . CICLURI . GRAFURI CONEXE . APLICAT  II ^IN MATEMATICA DE GIMNAZIU S I LICEU 27
AB, obt inem un graf cu nv^ arfuri , evident tot conex.Din ipoteza de induct ie
deducem c a noul graf are cel put in n1 muchii , deci graful init ial are cel put in
nmuchii.
Dac ad(A)2 , atunci toate v^ arfurile au gradul cel put in 2  si deducem din
teorema 1 , c a num arul de muchii este cel put in n+1 , mai mult dec^ at sucient.
Vom discuta ^ n continuare c^ ateva aplicat ii ale teoremei 2 .
Aplicat ia 4.21. Cei20de membri ai unui club de tenis au programat un mini-
turneu ^ n care se vor juca 14meciuri de simplu , astfel ^ nc^ at ecare membru
s a joace cel put in o dat a. S a se arate c a ^ n cadrul acestei program ari exist a o
submult ime de 6meciuri la care particip a 12juc atori diferit i .
(Olimpiada SUA , 198:)
S a consider am componentele conexe ale grafului asociat ( acela si ca ^ n prima
solut ie ) . Dac a avem kastfel de componente  si pentru componenta cu num arul
inot am cuvi, respectiv mi, num arul de v^ arfuri  si de muchii pentru acea
component a , avem , conform teoremei 2 mivi1 , pentru orice ia sadar
Pk
i=1miPk
i=1(vi1) =Pk
i=1vik,
adic a 1420k.
Deducem c a graful nostru are cel put in 6 componente conexe . Alegem c^ ate
o muchie din ecare ( posibil , c aci graful nu cont ine v^ arfuri izolate , c a ecare
membru joac a cel put in un meci ), obt inem cele 6 meciuri la care particip a 12
juc atori diferit i .
Aplicat ia 4.22. 23 de culori sunt folosite pentru a colora o pagin a de caiet
de matematic a , ecare p atr at el al paginii inde colorat cu o singur a culoare
. O pereche de culori se nume ste ,,asortat a" dac a exist a dou a p atr at ele vecine
colorate cu cele dou a culori . S a se determine num arul minim de perechi asortate
.
(Turneul Oras elor , 198:)
Consider am graful ^ n care v^ arfurile sunt cele 23 de culori, iar o muchie leag a
dou a v^ arfuri dac a respectivele culori sunt asortate. Cum din orice p atrat al
paginii putem ajunge ^ n orice alt p atrat folosind p atrate vecine , deducem c a
graful astfel construit este conex. Dar atunci, conform teoremei 2 , num arul
de muchii (deci de perechi asortate) este cel put in 22 . R am^ ane s a ar at am c a
exist a o colorare cu exact 22 de perechi asortate . Pentru aceasta , alegem 22 de
p atrate printre care s a nu e p atrate vecine , le color am cu 22 de culori diferite
, iar toate celelalte p atrate ale paginii le color am cu cea de-a 23-a culoare.
^Incheiem propun^ and cititorului dou a probleme legate de conexitate.
Aplicat ia 4.23. Fiek sitdou a numere naturale, prime ^ ntre ele , mai mari
dec^ at 1. Plec^ and de la permutarea (1;2;:::;n )a numerelor 1;2;:::;n , putem
schimba ^ ntre ele dou a numere dac a  si numai dac a diferent a lor ( ^ n modul ) este
egal a cuksau cut. S a se arate c a , aplic^ and de mai multe ori aceast a trans-
formare , putem obt ine orice permutare a numerelor 1;2;:::;n dac a  si numai
dac ank+t1.
(Ungaria , 2000)

28CAPITOLUL 4. APLICAT II ALESE DIN CONCURSURILE S COLARE S I OLIMPIADE ALE TEORIEI S IRURILOR S I SUBS IRURILOR
Aplicat ia 4.24. La o petrecere urmeaz a s a participe e p, eqpersoane ( unde
p siqsunt prime ^ ntre ele ). Gazda vrea sa e pregatit a pentru orice variant a  si
vrea s a taie dinainte tortul astfel ^ nc^ at s a poat a oferi port ii egale participant ilor ,
indiferent dac a vor  psauq. Care este num arul minim de p art i ( nu neap arat
egale ) ^ n care trebuie t aiat tortul?