Copyright\begin{matrix}c \\ ◯ \end{matrix}1999 ONG TCV Scoala Virtuala a Tanarului Matematician http://math.ournet.md 1

Principiul extremal

Ideea-cheie a solutionarii unui sir de probleme consta in studierea unei marimi (element, caracteristica) extremale. Aceasta metoda de rezolvare se numeste pricipiul extremal. Sa analizam cateva exemple.

Exemplul 1. Sa se demonstreze ca multimea numerelor prime de forma 4m + 3, m ∈ N, este infinita.

Rezolvare. Admitem contrariul, adica presupunem ca multimea numerelor prime de forma 4m + 3 este finita. Fie p_{1}, …, p_{n} elementele acestei multimi. Daca n este numar par, atunci

p_{1} · p_{2} · . . . · p_{n} + 2 ≡ (−1)^{n} + 2 ≡ 3 (mod 4),

adica p_{1} · p_{2} · . . . · p_{n} + 2 = 4m + 3 pentru un oarecare m ∈ N. Prin urmare acest numar are un divizor prim de forma p = 4k + 3 (in adevar, daca toti divizorii primi ai numarului 4m + 3 au forma 4k + 1, atunci si produsul lor va avea forma 4k + 1). Pe de alta parte, este usor de observat ca nici unul din numerele p_{1}, p_{2}, …, p_{n} nu sunt divizori ai numarului p_{1} ·p_{2} ·. . .·p_{n} +2. Prin urmare, p ∉ {p_{1}, p_{2}, …, p_{n}}. Contradictie cu ipoteza ca toate numerele prime de forma 4m + 3 se contin in multimea {p_{1}, p_{2}, …, p_{n}}.

Daca n este un numar impar, atunci

p_{1} · p_{2} · . . . · p_{n} + 4 ≡ (−1)^{n} + 4 ≡ 3 (mod 4).

Similar cazului precedent se arata existenta unui numar prim p de forma p = 4k + 3, astfel incat p ∉ {p_{1}, p_{2}, …, p_{n}}. Aceeasi contradictie.

Exemplul 2. Sa se demonstreze ca pentru orice n natural, numarul

1 + \frac{1}{3} + \frac{1}{5} + … + \frac{1}{2n + 1}  (1)

nu este natural.

Rezolvare. Fie 3^{r_{j}} puterea maximala a lui trei, ce divide numarul 2j + 1 (j = 0, 1, …, n) si 3^{r} = max{3^{r_{j}} | j = 0, 1, …, n}. Vom arata ca numai pentru un j ∈ {0, 1, …, n} are loc egalitatea r = r_{j}. Admitem contrariul. Fie j, k, ∈ {0, 1, …, n}, j ≠ k astel incat

2j + 1 = 3^{r} · s_{j}, 2k + 1 = 3^{r} · s_{k}.

Din forma numarului 3^{r}, rezulta 3^{r+1} > 2n+1. Prin urmare 1 ≤ 3^{r}·s_{j} < 3^{r+1}, 1 ≤ 3^{r}·s_{k} < 3^{r+1}, de unde rezulta, 1 ≤ s_{j} ≤ 2, 1 ≤ s_{k} ≤ 2. Cum s_{j} ≠ s_{k}, unul din aceste numere este par. Contradictie cu ipoteza.

Aducand expresia (1) la numitor comun se obtine

\frac{\frac{(2n + 1)!!}{1} + \frac{(2n + 1)!!}{3} + … + \frac{(2n + 1)!!}{2n + 1}}{(2n + 1)!!} ,  (2)

unde (2n + 1)!! = 1 · 3 · . . . · (2n + 1).

Fie r = r_{j} si 3^{m} puterea maximala a numarului trei ce divide numarul (2n + 1)!!. Atunci pentru fiecare k ≠ j din relatia 3^{m−r_{k}} |\frac{(2n + 1)!!}{2k + 1} rezulta ca 3^{m−r+1} |\frac{(2n + 1)!!}{2k + 1} . Pe de alta parte

3^{m−r+1} |\frac{(2n + 1)!!}{2j + 1} . Asadar

3^{m−r+1} |\frac{(2n + 1)!!}{1} + \frac{(2n + 1)!!}{3} + … + \frac{(2n + 1)!!}{2n + 1} ,

si, prin urmare, numarul (2) nu este natural.

Exemplul 3. Sa se demonstreze ca ecuatia

x^{2} + y^{2} = 3(z^{2} + t^{2})  (3)

nu are solutii in numere intregi pozitive.

Rezolvare. Presupunem contrariul, adica exista solutiile x, y, z, t a ecuatiei (3) in numere intregi pozitive. Din (3) rezulta ca 3|x^{2} + y^{2} si, prin urmare, 3|x si 3|y (rezulta din faptul ca restul impartirii patratului oricarui numar intreg la 3 este egal cu zero sau unu). Asadar, x = 3x_{1}, y = 3y_{1}. Prin urmare

z^{2} + t^{2} = 3(x_{1}^{2} + y_{1}^{2}).

In acelas timp, z^{2}+t^{2} < x^{2}+y^{2}. Contradictia obtinuta demonstreaza justetea afirmatiei initiale.

Exemplul 4. In plan este data multimea de puncte M. Fiecare punct din M este mijlocul unui segment, ce uneste alte doua puncte din M. Sa se demonstreze ca multimea M este infinita.

Rezolvare. Admitem contrariul - multimea M este finita. Consideram in plan un sistem cartezian de coordonate. Fie un punct din M cu abscisa maximala (daca asa puncte sunt mai multe - alegem acel punct care are ordonata maximala). Notam acest punct prin A(x, y), el este mijlocul unui segment ce uneste punctele B(x_{1}, y_{1}) si C(x_{2}, y_{2}) din M. Din relatiile x = \frac{x_{1} + x_{2}}{2} , x_{1} ≤ x, x_{2} ≤ x rezulta x_{1} = x_{2} = x, adica punctele A, B, C au aceeasi abscisa. Prin urmare y_{1} ≤ y, y_{2} ≤ y, ceea ce este imposibil, deoarece y = \frac{y_{1} + y_{2}}{2} , iar punctele A, B, C sunt distincte. Contrazicerea cu ipoteza, prin urmare multimea M este infinita.

Exemplul 5. Fiecare latura a unui patrulater este diametrul unui cerc. Sa se arate ca cercurile construite acopera patrulaterul.

Rezolvare.

[figure: A; M; C; B; D]

Notam patrulaterul dat ABCD (pe desen el este convex, dar rezolvarea ramane valabila si in cazul unui patrulater neconvex). Fie M un punct arbitrar din interiorul patrulaterului. Consideram unghiul maximal dintre unghiurile ^{}A̸MB, ^{}B̸MC, ^{}C̸MD, ^{}D̸MA. Fie, de exemplu, acest unghi ^{}A̸MB. Atunci ^{}A̸MB ≥ 90^{∘} (in caz contrar ^{}A̸MB + ^{}B̸MC+ +^{}C̸MD + ^{}D̸MA < 4 · 90^{∘} = 360^{∘}). Prin urmare, punctul M va fi acoperit de cercul, construit pe latura AB ca diametru.

Exemplul 6. Sa se arate, ca daca lungimile tuturor laturilor triunghiului sunt mai mici ca 1, atunci aria lui este mai mica decat \frac{\sqrt{3}}{4}.

Rezolvare.

[figure: A; B; C]

Fie in triunghiul △ABC ^{}A̸ este cel mai mic unghi. Atunci ^{}A̸ ≤ 60^{∘} si aria triunghiului se estimeaza astfel:

S = \frac{1}{2}AC · AB · sin A < \frac{1}{2} · 1 · 1 · sin 60^{∘} = \frac{\sqrt{3}}{4}.

Exemplul 7. In plan sunt date n (n ≥ 3) drepte, neparalele doua cate doua, astfel incat, prin punctul de intersectie a oricaror doua drepte dintre acestea, trece inca o dreapta. Sa se arate, ca toate dreptele trec printr-un punct.

Rezolvare. Admitem contrariul, adica exista asa o dreapta din familia data si exista asa punct de intersectie a altor doua drepte, ce nu apartin ei. Consideram distanta minimala (nenula) de la punctele de intersectie a dreptelor pana la drepte. Fie aceasta distanta este cea de la punctul A pana la dreapta l. Prin punctul A trec cel putin trei drepte.

[figure: A; Q; R; P; B; C; D; l]

Vom nota punctele de intersectie ale acestor drepte cu dreapta l prin B, C, D si vom cobora perpendiculara AP pe dreapta l. Cel putin doua dintre punctele B, C, D se afla de o parte in raport cu punctul P. Fie aceste puncte C si D, si P C < P D. Din punctele P si C coboram perpendicularele P Q si CR pe dreapta AD. Deoarece AP > P Q (ipotenuza triunghiului dreptunghic AP Q este mai mare decat cateta) si P Q ≥ CR, rezulta AP > CR. Contradictie.

Exemplul 8. In plan sunt situate n (n ≥ 3) puncte astfel incat aria oricarui triunghi cu varfurile in aceste puncte nu intrece 1. Sa se arate ca toate punctele pot fi inchise intr-un triunghi de aria 4.

Rezolvare.

[figure: A; B; C; C_{1}; A_{1}; B_{1}; D]

Consideram triunghiul de arie maxima cu varfurile in punctele date, fie acest triunghi - ABC. Prin punctele A, B, C ducem dreptele l_{A}, l_{B}, l_{C}, paralele cu laturile BC, CA, AB respectiv.

Notam triunghiul format de dreptele l_{A}, l_{B}, l_{C} prin A_{1}B_{1}C_{1}. Aria acestui triunghi este de 4 ori mai mare decat aria △ABC, deci ea nu intrece 4.

Vom arata ca fiecare din punctele date se contine in △A_{1}B_{1}C_{1}. Admitem contrariul, adica exista un punct D din multimea data de puncte, ce se afla de parti diferite cu unul din varfurile △A_{1}B_{1}C_{1} relativ la latura opusa acestui varf. Fie, de exemplu, punctele C_{1} si D se afla de parti diferite relativ la latura B_{1}A_{1}. Atunci distanta de la punctul D pana la AB este mai mare decat distanta de la punctul C pana la AB. Prin urmare, aria △ABD intrece aria △ABC, ceea ce contrazice alegeriea △ABC.

Exemplul 9. Sa se demonstreze, ca orice poligon convex de aria unu, poate fi inclus intr-un dreptunghi de aria doi.

Rezolvare.

[figure: E; Q; F; A; B; Q_{1}; P_{1}; C; P; D]

Fie AB diagonala maximala a poligonului. Prin punctele A si B ducem perpendiculare la segmentul AB. Din alegerea segmentului AB rezulta ca tot poligonul se contine in fasia formata de aceste perpendiculare. Ducem dreptele CD, EF, paralele la AB prin unele varfuri ale poligonului in conditie ca poligonul se afla de o singura parte in raport cu fiecare dintre aceste drepte. Din punctele P si Q coboram perpendicularele P P_{1} si QQ_{1} pe AB. Aria poligonului initial este mai mare sau egala ca suma ariilor △AP B si △AQB, adica este nu mai mica decat

\frac{1}{2}AB · P P_{1} + \frac{1}{2}AB · QQ_{1} = \frac{1}{2}CD · CE.

De aici rezulta, ca aria dreptunghiului EF DC, ce contine poligonul dat, nu intrece 2 (un.arie).

Exemplul 10. In plan sunt date patru puncte necoliniare. Sa se arate, ca cel putin un triunghi cu varfurile in aceste puncte nu este ascutitunghic.

Rezolvare.

[figure: 6; 1; 2; 7; 3; 5; 4]

Consideram un triunghi arbitrar cu varfurile in aceste puncte. Dreptele, construite pe laturile acestui triunghi impart planul in 7 parti. Apar urmatoarele cazuri:

I caz

[figure: A; B; C; D]

Al patrulea punct este situat pe una din aceste drepte. In asa caz trei, fie punctele A, B, C, formeaza triunghiul, iar al patrulea punct, fie D, se afla pe una din laturi. Evident, cel mai mare dintre unghiurile ^{}A̸DB, ^{}C̸DB nu este ascutit. Prin urmare, cel putin unul dintre triunghiurile ADB, CDB nu este ascutiunghic.

Cazul II.

[figure: A; B; D; C]

Al patrulea punct se afla in una din partile 2, 4, 6, 7. In asa caz exista asa un triunghi ABC cu varfurile in punctele date si care contine in interiorul sau punctul D. Cel mai mare dintre unghiurile ^{}A̸DC, ^{}C̸DB, ^{}B̸DA este nu mai mic de 120^{∘}, prin urmare cel putin unul dintre triunghiurile ADC, CDB, BDA nu este ascutitunghic.

Cazul III.

[figure: A; B; C; D]

Al patrulea punct se afla in una din partile 1, 3, 5. In asa caz cele patru puncte sunt varfurile unui patrulater convex ABCD. Cel mai mare dintre unghiurile ^{}A̸BC, ^{}B̸CD, ^{}C̸DA, ^{}D̸AB este mai mare sau egal cu 90^{∘}. Prin urmare cel putin unul dintre triunghiurile ABC, BCD, CDA, DAB nu este ascutitunghic.

Exemplul 11. Sapte ciupercari au strans impreuna 100 de ciuperci, dar oricare doi din ei n-a strans acelasi numar de ciuperci. Sa se demonstreze, ca sunt trei ciupercari, ce au cules impreuna nu mai putin de 50 ciuperci.

Rezolvare. Consideram trei ciuperci ce au strans impreuna numarul maximal de ciuperci (dintre toate tripletele posibile de ciupercari). Daca numarul minimal de ciuperci stranse (dintre acesti trei ciupercari alesi) este 16, atunci impreuna ei au strans cel putin 16 + 17 + 18 = 51 ciuperci.

Daca numarul minimal indicat este mai mare decat 15, atunci cei patru ciupercari ramasi au strans cel mult 14 + 13 + 12 + 11 = 50. Prin urmare, si in acest caz primii trei au strans nu mai putin de 50 de ciuperci.

Exemplul 12. Elementele unui tabel n × n sunt zerouri si unitati. Tabelul este completat astfel incat daca la intersectia unei linii si coloane se afla un zerou, atunci suma elementelor de pe linia si coloana ce contin acest zerou este nu mai mica decat n. Sa se demonstreze ca suma celor n^{2} numere din tabel nu este mai mica decat \frac{n^{2}}{2} .

Rezolvare. Consideram coloana (linia) ce contine suma minimala a elementelor ei. Fie aceasta suma egala cu k. Daca k ≥ \frac{n}{2}, atunci sumele elementelor celorlalte coloane (linii) nu este mai mica ca \frac{n}{2} si, prin urmare, suma tuturor elementelor nu este mai mica ca \frac{n^{2}}{2} . Fie k < \frac{n}{2}. Atunci in aceasta coloana (linie) sunt n − k zerouri. Prin urmare, suma elementelor fiecarei linii (coloane), ce contine un zerou din cele indicate este nu mai mica decat n − k.

Asa coloane sunt n − k, prin urmare suma elementelor lor este nu mica decat (n − k)^{2}. Suma elementelor in cele k linii (coloane) ramase nu este mai mica decat k, si prin urmare, suma elementelor lor este mai mare sau egala cu k^{2}. Asadar, suma tuturor elementelor este nu mai mica decat

(n − k)^{2} + k^{2} = 2 (\frac{n}{2} − k)^{2} + \frac{n^{2}}{2} ≥ \frac{n^{2}}{2} .

Exercitii pentru recapitulare

1. Sa se demonstreze ca multimea numerelor simple de forma 6m + 5, m ∈ N, este infinita.

2. Sa se arate, ca pentru orice numar natural n, n > 1, numarul

1 + \frac{1}{2} + … + \frac{1}{n}

nu este intreg.

3. Sa se demonstreze, ca ecuatia

x^{2} + y^{2} + z^{2} = 2^{1999}

nu are solutii in numere intregi.

4. Intr-o tara sunt 100 de aeroporturi si distanta dintre oricare doua din ele este diferita. Din fiecare port decoleaza un avion si zboara spre cel mai apropiat de el port. Sa se demonstreze ca nici intr-un port nu pot ateriza mai mult de 5 avioane.

5. In plan este data o multime finita de puncte. Orice dreapta ce trece prin doua din punctele date, contine inca un punct din multimea data. Sa se arate, ca toate punctele date se afla pe o dreapta.

6. Lungimile bisectoarelor unui triughi nu intrece 1cm. Demonstrati ca aria lui nu intrece

\frac{1}{\sqrt{3}}.

7. Sa se demonstreze ca intr-un pentagon convex exista trei diagonale, din care se poate forma un triunghi.