Elemente de Logica Si Rationament Matematic

În logică, prin propoziție înțelegem un enunț care poate fi ori adevărat ori fals. Oricărei propoziții i se asociază o valoare de adevăr: este sau adevărată – și atunci spunem că are valoarea de adevăr 1 – sau este falsă – și atunci spunem că are valoarea de adevăr 0. Nici o propoziție nu este în același timp și adevărată și falsă.

Exemple de propoziții:

“2 + 3 = 6”

“București este capitala României”

“5 este număr prim”

Prima din aceste propoziții are valoarea de adevăr 0, celelalte două au valoarea de adevăr 1.

Propozițiile interogative sau exclamative ale limbii nu sunt propoziții în logică. De asemenea, definițiile nu sunt propoziții. De exemplu, enunțul "un număr întreg divizibil cu 2 se numește număr par" nu este o propoziție. Însă enunțul “orice număr par este divizibil cu 2” este propoziție și are valoarea de adevăr 1.

1.2 Operatori logici

Cu ajutorul operatorilor logici, din una sau două propoziții date se pot forma noi propoziții a căror valoare de adevăr depinde numai de valoarea de adevăr a propozițiilor date. Vom indica această valoare de adevăr cu ajutorul unor tabele: în partea stângă a tabelului apar toate valorile de adevăr posibile ale propozițiilor date iar în partea dreapta, valoarea de adevăr a propoziției nou formate.

Operatorii logici sunt: (negația),  (disjuncția)  (conjuncția),  (implicația),  (echivalența).

Negația

Exemplu

Propoziția b = "nu este adevărat că 7 este număr par" care coincide cu "7 nu este număr par" este negația propoziției

a = "7 este număr par"

Propoziția a este falsă și propoziția b = a este adevărată.

Disjuncția propozițiilor

Exemplu

Propoziția: "5 este număr prim sau 8 este număr impar" este adevărată. fiind disjuncția a două propoziții dintre care una este adevărată.

Conjuncția propozițiilor

Exemplu

Propoziția: "5 este număr prim și 8 este număr impar" este o propoziție falsă fiind conjuncția a propozițiilor: "5 este număr prim" și "8 este număr impar”, prima fiind adevărată iar a doua falsă.

Implicația propozițiilor

Exemple

Propoziția: "dacă 5 este număr prim, atunci 6 + 2 = 4" este o propoziție falsă fiind o implicație a cărei sursă este o propoziție adevărată.

Propoziția "dacă 2 + 2 = 5, atunci 6 este număr impar" este adevărată fiind o implicație a cărei sursă este o propoziție falsă.

Dacă propoziția a  b este adevărată, scriem a  b și spunem. că, b este o consecință logică a lui a.

De exemplu avem:

"2 + 2 = 5”  "6 este număr impar"

dar nu avem (nu este adevărat că) "5 este număr prim"  "6 + 2 = 4".

Echivalența propozițiilor

Exemplu

Propoziția: "4 > 5 dacă și numai dacă 1 + 1 = 3" este o propoziție adevărată, fiind echivalența a două propoziții ambele false.

Dacă propoziția a  b este adevărată, scriem a  b și spunem că propozițiile a și b sunt echivalente logic.

1.3 Legile calculului propozițional

Calculul propozițional studiază din punct de vedere logic expresiile obținute din literele p, q, r, …, cu ajutorul operatorilor logici: ,,,, după anumite reguli. Literele p, q, r, …, se numesc variabile propoziționale sau formule elementare iar expresiile obținute din ele cu ajutorul operatorilor logici se numesc formule, regulile de formare a formulelor fiind următoarele:

variabilele propoziționale p, q, r, …, sunt formule;

dacă A și B sunt formule, atunci A, A  B. A  B, A  B și A  B sunt formule.

Exemple

Expresiile:

p, (p). ((r  s)  (p)), (r  (s  (p)), ((p  (q)  (p  q))

sunt formule ale calculului propozițional.

Deoarece abundența parantezelor în unele formule devine greoaie, perechea de paranteze exterioare nu se mai scrie, iar ordinea în care se aplică operatorii logici este următoarea: , , , , . Astfel, expresiile date ca exemple mai sus se scriu astfel:

p, p. r  s p, r  (s p), p q  (p  q)

Dacă într-o formulă în scrierea căreia intră variabilele propoziționale p, q, r, … înlocuim aceste variabile cu diverse propoziții, obținem o nouă propoziție a cărei valoare de adevăr depinde numai de valoarea de adevăr atribuită variabilelor propoziționale componente. O formulă a calculului propozițional se numește lege, tautologie sau formulă identic adevărată dacă orice valoare de adevăr ar avea variabilele propoziționale care intră în compunerea sa, valoarea de adevăr a propoziției obținute este 1.

Pentru a demonstra că o anumită formulă a calculului propozițional este o tautologie, atribuim variabilelor propoziționale care intră în compunerea ei valori de adevăr în toate modurile posibile și calculăm de fiecare dată, pe baza tabelelor de adevăr ale operatorilor logici, valoarea de adevăr a formulei; dacă de fiecare dată valoarea de adevăr obținută este 1, înseamnă că formula respectivă este o tautologie.

Exemple:

Legea terțului exclus

 Legea negării implicației:

 Legea silogismului:

În virtutea acestor tautologii putem scrie:

(p  q)  p q

(p  q)  (q  r)  (p  r)

Alte exemple de tautologii, ale căror demonstrații se pot realiza în mod analog, sunt:

Legile calculului propozițional și în special cele date mai sus ca exemple sunt importante deoarece pe baza lor se fac raționamentele logice și deci demonstrațiile în matematică.

1.4 ELEMENTE DE CALCULUL predicatelor

Noțiunea de predicat are o importantă deosebită în matematică. Fără a exagera, aproape orice teoremă din matematică este un enunț ce conține unul sau mai multe predicate.

Un enunț care depinde de una sau mai multe variabile și are proprietatea că pentru orice “valori” date variabilei corespunde o propoziție adevărată sau falsă se numește predicat sau propoziție cu variabile. Predicatele sunt unare, binare, ternare etc., după cum depind respectiv de 1, 2, 3 variabile. Ori de câte ori definim un predicat trebuie să indicăm și mulțimile în care variabilele iau valori.

Cuantificatorul existențial (Ǝ) și cuantificatorul universal (∀)

Strâns legată de noțiunea de predicat apare noțiunea de cuantificator. Fie predicatul unar p(x) unde x desemnează un element oarecare din multimea E. Putem formula enunțul: există cel puțin un x din E astfel încât p(x), care se notează (Ǝ x)p(x). Acest enunț este o propoziție care este adevărată când există cel puțin un element x0 din E astfel încât propozitia p(x0) este adevaratasi este falsa cand nu exista nici un x0 din E astfel incat p(x0) să fie adevărată. Cu predicatul p(x) putem forma și enunțul : oricare ar fi x din E are loc p(x) care se notează (∀x) p(x). Acest enunț este o propoziție care este adevarată dacă pentru orice element x0 din E p(x0) este adevărată, fiind falsă în cazul în care există cel puțin un x0 din E pentru care E p(x0) este falsă.

Echivalența predicatelor. Două predicate p( x, y, z), q(x, y, z) se zic echivalente și scriem p( x, y, z)⇔ q(x, y, z) dacă oricum am alege valorile variabilelor x0 , y0, z0 pentru care propoziția p(x0 , y0, z0 ) și q(x0 , y0, z0 ) au aceeași valoare de adevăr. Dacă oricum am alege valorile variabilelor x0 , y0, z0 pentru care propoziția p(x0 , y0, z0 ) este adevărată rezultă că și propoziția q(x0 , y0, z0 ) este adevărată, vom scrie p( x, y, z)⇒ q(x, y, z). Se vede că p( x, y, z)⇔ q(x, y, z) atunci și numai atunci când p( x, y, z)⇒ q(x, y, z) și q( x, y, z)⇒ p(x, y, z)

Reguli de negatie. Fie p(x) un predicat unar, unde x desemneaza un element din multimea E. Atunci :

1)    ((Ǝ) p(x)) ≡(∀x) p(x)

2)    ((∀x) p(x) ≡( Ǝx) p(x)

(aici semnul ≡ desemnează faptul că cele două prop. au aceeși valoare de adevăr)

1.5 TEOREMA

1.Structura unei teoreme. O clasă foarte largă de propoziții adevărate o constituie teoremele din matematică.

Exemple : a) În orice triunghi, suma măsurilor unghiurilor sale este egală cu 180o .

b) În orice triunghi, lungimea oricărei laturi este mai mică decât suma lungimilor celorlalte două și mai mare ca diferența lor

c) În orice triunghi dreptunghic pătratul lungimii ipotenuzei este egal cu suma pătratelor lungimilor catetelor.

Fiecare teoremă stabilește că un obiect matematic sau un ansamblu de obiecte matematice posedă o anumită proprietate. Cum se obțin teormele? Studiind matematica elementară se poate constata că toate teoremele ei se deduc prin demonstrații, adică printr-un șir de raționamente logice, sau cum se mai spune, prin silogisme, din câteva propoziții fundamentale numite axiome, care se acceptă a fi adevărate fără demonstrație.

Aproape orice teoremă se poate enunța sub forma ,,dacă…, atunci…’’. Partea întâi, care începe cu cuvântul dacă se numește ipoteza teoremei, partea a doua, cea care începe cu cuvântul atunci se numește concluzia teoremei.

Să luăm de exemplu teorema : ,, într-un triunghi dreptunghic pătratul lungimii ipotenuzei este egal cu suma pătratelor lungimilor catetelor’’. Această teoremă se poate pune sub forma : ,,dacă ABC este un triunghi dreptunghic, atunci pătratul lungimii ipotenuzei este egal cu suma pătratelor lungimilor catetelor’’. Aici ipoteza este ,, ABC este un triunghi dreptunghic’’ iar concluzia este ,,pătratul lungimii ipotenuzei este egal cu suma pătratelor lungimilor catetelor’’.

Teoremele se pot pune sub forma implicației: (1) p(x, y, z…)⇒ q(x, y, z) care reprezintă notația prescurtată a propoziției (1’) (∀x)( ∀y)( ∀z).. p(x, y, z…)→ q(x, y, z) În implicatia (1) predicatul p(x, y, z…) constituie ipoteza teoremei, iar q(x, y, z) constituie concluzia teoremei.

2.Teorema contrară. Să considerăm următoarea teoremă: ,,dacă un patrulater este pararelogram, atunci diagonalele sale se taie în părți egale’’. Din această teoremă formăm următorul enunț : dacă un patrulater nu este paralelogram, atunci diagonalele sale nu se taie în părți egale. Acest enunț este o propoziție adevărată, deci o teoremă. Cum am obținut acestă nouă teoremă? Se observă că ea s-a obținut din prima, înlocuind ipoteza și concluzia prin negațiile lor.

Fiind dată o teoremă, propoziția care se obține din teorema dată înlocuind ipoteza și concluzia ei prin negațiile lor se numește contrara teoremei date . În cazul că această propoziție este adevărată ea se numește teorema contrara teoremei date.

Observație. Pentru a enunța corect contrara teoremei, este foarte important să știm să negăm corect.

În termeni ai calculului cu predicate dacă

(1)     p(x, y, z…)⇒ q(x, y, z) este teorema dată, atunci contrara teoremi este propoziția (2) (∀x)( ∀y)( ∀z)..( p(x, y, z…)→ q(x, y, z))

În cazul că (2) este o propoziție adevărată atunci (2) se scrie sub forma

(2)     p(x, y, z…)⇒ q(x, y, z)

și constituie teorema contrară a teoremei (1).

Capitolul II

CÂTEVA PRINCIPII DE REZOLVARE A PROBLEMELOR DE

MATEMATICĂ

2.1 Principiul parității

În matematica elementară întâlnim multe probleme care folosesc noțiunea de paritate. Principiul parității constă în separarea cazurilor pare și impare

dintr-o situație. Regulile parității:

– suma a două numere pare este un număr par

– suma a două numere impare este un număr par

– suma dintre un număr par și altul impar este un număr impar

– produsul a dou numere pare este un număr par

– produsul a dou numere impare este un număr impar

– produsul dintre un număr par și un număr impar este un număr par.

Prezint în continuare câteva probleme rezolvate ce folosesc principiul

parității.

1. Demonstrați că dacă suma a două numere întregi este un număr impar, produsul lor este un număr par.

Soluție. Fie a și b numerele. Din ipoteză a + b = 2n + 1, n ϵ N. Deci unul din numerele a sau b este par. Fie a = 2k, atunci b = 2n + 1 – a = 2n + 1 – 2k = 2(n – k) + 1, adică b este impar. Atunci a∙b esre produsul dintre un număr par și altul impar, deci va fi impar.

2. Demonstrați că 2n (n ≥2, n ϵ N ) se poate scrie ca o sumă de două

numere naturale impare consecutive, iar 3n se poate scrie ca o sumă de trei numere naturale consecutive și ca sumă a trei numere impare consecutive.

Soluție. Pentru orice n ≥2 , n ϵ N, 2n este număr par. Avem: 2n = 2∙2n-1=

2n-1 + 2n-1 = (2n-1 – 1) + (2n-1 + 1). Pentru n ≥2, n ϵ N, 2n-1 – 1 și 2n-1 + 1 sunt impare consecutive.

Pentru orice n ≥ 2, n ϵ N, 3n ϵ N și 3n = 3∙3n-1 = 3n-1 + 3n-1 + 3n-1= (3n-1-1) + 3n + (3n-1+1). Numerele 3n-1-1, 3n și 3n-1+1 sunt consecutive pentru n ≥2. Mai avem că 3n = 3∙3n-1 = 3n-1 + 3n-1 + 3n-1 = (3n-1 – 2) + 3n-1 + (3n-1 + 2), unde 3n-1 – 2, 3n-1,

3n-1+2 sunt impare consecutive.

3. Se consideră șirul numerelor naturale de la 1 la 1979 adică:

1,2,3,4,..,1977,1978,1979. Luați la întâmplare oricare două numere din acest șir și înlocuiți-le cu modulul diferenței lor. La fiecare operație de acest fel numărul numerelor din șir scade cu unu (fiindcă am înlocuit două numere cu unul) și vom obține, în final, un singur număr. Arătați că acest număr este par.

Soluție. La fiecare etapă a operației descrise, numărul numerelor impare din șir rămâne neschimbat sau descrește cu doi, deoarece dacă, în primul caz, luăm un număr par și unul impar, modulul diferenței lor este impar, deci numărul impar l-am înlocuit cu altul impar, iar în al doilea caz dacă luăm două numere impare, modulul diferenței lor este un număr par, deci numărul numerelor impare scade cu doi. În șirul 1,2,3,..,1979 avem (1+1979):2 numere impare, adică 990.

La fiecare pas rămâne un număr par de numere impare și atunci ultimul număr va fi cu siguranță par.

4. Se consideră numerele impare k,n1,n2,…,nk. Să se demonstreze că

printre numerele: , … , , există un număr impar de

numere impare.

Soluție. Suma a două numere impare este un număr par, deci numerele

, … , sunt naturale. Sa presupunem ca printre acestea se află un număr par de numere impare. Atunci suma lor + … = n1+n2+…+nk este un număr par. Dar aceeași sumă este suma unui număr impar de numere impare, deci este un număr impar. Contradicție. Deci presupunerea făcută a fost falsă, deci printre numerele considerate în ipoteză există un număr impar de numere impare.

2.2 Principiul lui Dirichlet

Matematicianul german Peter Gustav Dirichlet (1805-1859) a elaborat un principiu extrem de simplu cu aplicații neașteptate în variate domenii, principiu care-i poartă numele și pe care-1 enunțăm mai jos, fiind o metodă de demonstrație de tipul următor.

"Dacă repartizăm n +1 obiecte în n cutii, atunci cel puțin două obiecte vor fi în aceeași cutie."

Justificare: Considerăm cazul cel mai nefavorabil așezând în fiecare cutie câte un obiect. Deci am folosit n cutii și n obiecte. Obiectul cu numărul

n +1 trebuie pus și el într-o cutie oarecare. Dar în acea cutie există deja un obiect. Așadar în acea cutie există deja un obiect pus anterior. In acea cutie vor fi două obiecte.

Forma generală a principiului lui Dirichlet este următoarea:

"Dacă așezăm kn +1 obiecte în n cutii, atunci cel puțin k +1 obiecte, k ϵ N, vor fi în aceeași cutie."

Teorema 2.2.1. (Principiul lui Dirichlet) Fie A o mulțime nevidă iar A1, A2,…, An o partiție a lui A (adică =A iar AiAj= , pentru i j).

Dacă avem n+1 elemente a1,a2,…, an, an+1 din A, atunci există o submulțime Ai a partiției care să conțină cel puțin două elemente ale mulțimii {a1, a2,…, an, an+1 }.

În literatura matematică principiul lui Dirichlet este întâlnit și sub denumirea de "principiul cutiei", cu precizarea că denumirea de "cutie" desemnează "grupe de obiecte", stabilite după anumite criterii, iar "obiectele" desemnează lucruri, numere, figuri geometrice, etc. Prezint în continuare câteva probleme ale căror soluții se bazează pe principiul de mai sus.

Aplicații.

Fie a1, a2,…, an, an+1 un șir de n+1 numere întregi diferite două câte două. Atunci există doi indici i, j l, 2, …,n+l} astfel încât aiaj (mod n).

Soluție. Împărțim mulțimea în cele n clase de resturi modulo n. Cum acestea formează o partiție a lui , totul rezultă din principiul lui Dirichlet.

Fie M o mulțime formată din n numere întregi (nu neapărat distincte). Să se demonstreze că M are cel puțin o parte nevidă cu proprietatea că suma elementelor sale se divide cu n.

(Gh. Szlsy)

Soluție. Fie M = {a1, a2,…, an} cu aiZ, pentru orice i{l, 2, …, n}. Să considerăm submulțimile lui M: M1 = {a1}, M2 = {a1, a2}, …, Mn = { a1, a2,…, an } și să formăm sumele: S1 = a1, S2 = a1 + a2,…, Sn = a1 + a2 +…+ an. Dacă unul din numerele S1, S2,…, Sn se divide cu n, problema este rezolvată. Dacă S1, S2, …. Sn nu se divid la n, atunci conform aplicației anterioare există p, k N, k<pn, astfel încât Sp Sk(mod n). Atunci mulțimea căutată va fi {ak+1, ak+2 , …,ap}.

Se dă un cub cu latura 1. Să se arate că oricum am alege 28 de puncte interioare, cel puțin două dintre ele au distanța mai mică sau egală cu .

Soluție. Să împărțim fiecare muchie a cubului în câte trei părți egale și ducând prin ele paralele la muchii obținem pe fiecare față a cubului 9 pătrate egale. Ducând plane paralele cu fețele cubului prin punctele de diviziune, cubul este astfel împărțit în 27 de cubulețe, fiecare având latura . Cum sunt 28 de puncte interioare, conform pricipiului lui Dirichlet, cel puțin două se vor afla în interiorul aceluiași cubuleț de latură . Distanța maximă dintre cele două puncte nu poate depăși diagonala unui astfel de cubuleț, care este.

Fiind date 9 puncte în interiorul pătratului unitate, să se demonstreze că există printre ele trei puncte, care să fie vârfurile unui triunghi, de arie mai mică sau egală cu .

Soluție. Unind două câte două mijloacele laturilor opuse în pătratul dat obținem o împărțire a acestuia în patru pătrate de arie . Conform principiului lui Dirichlet cel puțin unul dintre acestea va conține trei sau mai multe puncte din cele 9 considerate în enunț. Notăm EFGH acest pătrat și fie A, B, C trei dintre aceste puncte conținute în pătratul EFGH de latură obținut ca mai înainte (vezi Fig. 1); va fi suficient să probăm că Sabc SEFGH . Ducând prin A, B, C paralele la EH, una din ele se va afla între celelalte două, deci va tăia în interior latura opusă prin care aceasta trece. Fie AA' aceasta, cu A'BC; construim BB'AA' cu B' AA' și CC' AA' cu C' AA'.

Avem Sabc = Saba’ + Saca’ = AA' BB' + AA' CC' =

= AA’ (BB' + CC') EH HG = SEFGH

Fig. 1

Observație. în cazul în care punctele A, B, C sunt coliniare, demonstrația nu poate fi făcută în acest mod, însă atunci SABC = 0.

2.3 Principiul invariantului

Invariantul este o mărime, o relație, sau o proprietate care rămâne neschimbată în urma aplicării sau intervenției unei transformări.

Deci o situație inițială este supusă în mod repetat unor transformări. De obicei se cere să se demonstreze că în urma acestor transformări nu se poate ajunge la o anumită formă. Aceasta se poate face alegând caracteristica obiectului care a fost supus transformării, adică "invariantul" transformării. Dacă în final obiectul nu posedă "invariantul" atunci el nu poate fi obținut în urma transformărilor descrise.

Probleme

1. Considerăm un număr natural căruia îi schimbăm în mod arbitrar ordinea cifrelor. Este posibil ca diferența dintre numărul inițial și cel final să fie 2003?

Soluție. Restul împărțirii numărului la 9 este același cu restul împărțirii sumei cifrelor sale la 9. Suma cifrelor este aceeași, rezultă că restul împărțirii numărului la 9 este un invariant.

2. Pe o tablă sunt scrise semne de "+" și "-". Ștergem două semne și le înlocuim cu un semn, după următoarea regulă: dacă cele două semne șterse sunt identice le înlocuim cu "+", iar dacă ștergem două semne diferite le înlocuim cu "-". Arătați că ultimul semn care rămâne după un număr de pași nu depinde de ordinea alegerii perechilor.

Soluție. În acest caz paritatea numărului de minusuri va fi invariantul. Dacă la început numărul de minusuri este impar, ultimul semn care va rămâne este minus, iar dacă la început numărul de minusuri este par, la sfârșit va rămâne plus.

3. Trei greieri se găsesc pe o dreaptă în ordinea: A, B, C. Ei încep să sară capra, adică să sară unul peste altul (dar nu peste doi odată). Pot fi în aceeași ordine după 2003 sărituri?

Soluție. În urma unei sărituri de acest fel numărul perechilor de greieri inversați crește sau se micșorează cu 1 (proprietatea invariantă). După un număr impar de sărituri (2003) va exista un număr impar de perechi de greieri inversați. Deci nu se poate obține ordinea inițială (ce nu conține o astfel de pereche).

4. O cameră are dimensiunile podelei de 7m și 10m. În cele patru colțuri ale camerei se așează câte un dulap având baza pătrat cu latura de l m. Să se arate că ce rămâne din suprafața podelei nu poate fi acoperită cu plăci dreptunghiulare de dimensiuni 3 m x l m.

Soluție. Se împarte camera într-o rețea de pătrate cu latura l m pe care le vopsim în trei culori: roșu, alb, negru ca mai jos:

RANRANRANR

ANRANRANRA

NRANRANRAN

RANRANRANR

ANRANRANRA

NRANRANRAN

RANRANRANR

Obținem 24 de R, 23 de A, 23 de N. Eliminând colțurile rămân 20 de pătrățele roșii, 23 de pătrățele albe, 23 de pătrățele negre. Dar oricum am așeza o placă de 3×1 ea acoperă un pătrățel roșu, unul alb și unul negru. Dacă s-ar putea acoperi suprafața cu un număr întreg de plăci ar trebui să existe același număr de pătrățele pentru fiecare culoare.

2.4 Principiul inducției matematice

Procesul prin care din propoziții generale se obțin propoziții particulare se numește deducție. Un alt raționament logic este inducția matematică. Acest raționament conduce de la propoziții particulare la propoziții generale.

Inducția matematică poate fi completă și incompletă. Propun căteva exemple.

În continuare vom vedea în ce constă inducția matematică completă, unde este aplicată ea ca metodă.

Raționamentul logic prin care din propoziții particulare se obțin propoziții generale se numește inducție.

Deosebim inducție incompletă, pentru care propoziția generală se formulează în baza examinării unor cazuri particulare posibile, și inducție completă, pentru care propoziția generală se formulează în baza examinării tuturor cazurilor particulare posibile.

În baza exemplelor din manual împreună cu elevii am observat că prin inducție incompletă nu întotdeauna din propoziții particulare se obțin propoziții generale adevărate.

În multe exerciții și probleme se cere să se demonstreze anumite proprietăți ce depind de un număr natural n.

Asemenea probleme se soluționează în majoritatea cazurilor cu ajutorul principiului inducției matematice complete care are la bază următoarea teoremă:

Teorema 2.4.1. Dacă o proprietate P(n) (depinzând de un număr natural n) este adevărată pentru n=0 și pentru orice n este adevărată implicația logică:

„ P(n) adevărată P(n+1) adevărată”, atunci P(n) este adevărată pentru orice n.

Principiul inducției matematice se mai enunță și sub următoarele forme generalizate:

Teorema 2.4.2. Dacă o proprietate P(n) (depinzând de un număr natural n) este adevărată pentru o valoare particulară k a lui n (deci P(k) adevărată) și dacă

pentru orice număr arbitrar n k este adevărată implicația logică: „P(n) P(n+1)”, atunci P(n) este adevărată pentru orice n k.

Teorema 2.4.3. Dacă P(n) este o proprietate ce depinde de numărul natural n iar P(n) este adevărată pentru o valoare particulară k a lui n și dacă pentru orice număr natural n k este adevărată implicația logică: ,,P(m) adevărată, pentru orice m = k, k+1,…,n-l P(n) adevărată”, atunci P(n) este adevărată pentru orice n k.

Teorema 2.4.4. Dacă o proprietate P(n) este adevărată pentru p valori consecutive particulare ale lui n: n = k, k+1,…, k+p-1, (k, p N) și dacă pentru orice număr arbitrar n k este adevărată implicația logică: ,,P(n) P(n+p)”, atunci P(n) este adevărată pentru orice n k.

Aplicații.

Să se demonstreze că dacă m și n sunt numere naturale nenule (m n), atunci numărul soluțiilor naturale de componente nenule ale ecuației x1 + x2 +… + xn =m este

Soluție. Vom demonstra prin inducție matematică relativ la n.

Fie Nn(m) numărul căutat. Evident N1(m) = 1 =

Să presupunem că Nk(m) = , pentru k = 1, 2, …, n-l și să demonstrăm că Nn(m) = . Evident Nn(m) = Nn-1(m-1) + Nn-1(m-2) +…+ Nn-1(n-l) = + + … + .Conform principiului inducției matematice, Nn(m) = , pentru orice nN.

Să se demonstreze că orice orice număr natural n se poate scrie sub forma n = =m+3q cu m, q N.

Soluție. Pentru n natural să notăm cu P(n) proprietatea din enunț.

Vom proba că P(4), P(5) și P(6) sunt adevărate.

Într-adevăr, 4 = l + 3 – l (m=l,q=l)

5 = 2 + 3- l ( m = 2,q=l)

6 = 0 + 3- 2 (m = 0, q = 2) .

Să arătăm acum că este adevărată implicația logică: ,,P(n) P(n+3)”, și

atunci P(n) va fi adevărată pentru orice n 4, ținând cont de varianta generalizată a inducției matematice.

Într-adevăr, din n = m+3q rezultă n+3 = m+3(q+l).

Observație. Problema se mai poate soluționa și ținând cont de teorema împărțirii

cu rest.

Să se demonstreze că orice număr natural n 1 admite o reprezentare de forma

n = a1l2 + a2 22 +…+ann12, unde ai{-l, +1} pentru orice i = 1, 2, …, n1 (n1N, nu depinde de n).

Soluție. Să demonstrăm la început că dacă notăm prin P(n) proprietatea cerută de enunțul problemei, atunci P(l), P(2), P(3) și P(4) sunt adevărate.

Într-adevăr, pentru n = 1 avem 1=1 l2, cu a1 = 1;

pentru n = 2 avem 2 = (-l)12 +(-l)22 +(-l)32 +142 cu a1 = -l, a2 = -l, a3 =-l, a4 = 1;

pentru n = 3 avem 3 =(-l)12 +1 22 cu a1 = -1, a2 = 1;

pentru n = 4 avem 4 = (-1) l2 +(-l) 22 +1 32 cu a1= -l, a2 = -l, a3 = 1

Să presupunem acum că P(n) este adevărată pentru o valoare oarecare a lui n și să demonstrăm că este adevărată și P(n+4).

Pentru aceasta vom ține cont de identitatea:

(n+1)2 – (n+2)2 – (n+3)2 + (n+4)2 = 4.

Astfel, dacă n= , cu ai {-l, +1}, atunci

n + 4 = + (n1+1)2 – (n1+2)2 – (n1+3)2 + (n1+4)2 = ,

cu a=1, a=-1, a=-1, a=1.

Conform principiului inducției matematice generalizate, P(n) va fi adevărată pentru orice număr natural n 1.

Să se arate că pentru orice număr natural n, numărul En= (n+l)(n+2)…(n+n) se divide prin 2n dar nu se divide prin 2n+1.

Soluție. Fie P(n) proprietatea din enunțul exercițiului.

Vom demonstra că P(l) și P(2) sunt adevărate și că pentru orice număr natural n este adevărată implicația logică:,,P(n) P(n+2)’’

Avem E1=2 și evident 2 | E1 , dar 22 = 4 | E1 ; E2=12 și evident 22 = 4 | E2 dar 23= 8 | E2. Să presupunem acum că pentru un număr natural n, P(n) este adevărată, adică 2n |En dar 2n+1 | En. Deci En = 2n ∙ p, cu p impar. Atunci

En+2=(n+3)(n+4)…(2n)(2n+l)(2n+2)(2n+3)(2n+4)=

=4(n+l)(n+2)(n+3)… (2n)(2n+l )(2n+3)=

=22En(2n+l )(2n+3)=22 ∙2n ∙ p ∙ (2n+l)(2n+3)=2n+2∙p∙ (2n+l)(2n+3)=2n+2 ∙ p', unde p’= p(2n+l)(2n+3). Cum p' este impar rezultă că 2n+2 | En+2 și 2n+3 | En+2, adică P(n+2) este adevărată.

Conform principiului inducției matematice, P(n) este adevărată pentru orice nN.

Să se demonstreze că dacă a1,…,an sunt numere reale pozitive, atunci:

(cu egalitate când numerele sunt egale).

Se cunosc mai multe soluții pentru această inegalitate cunoscută sub numele de inegalitatea mediilor.

În cele ce urmează vom prezenta două soluții folosind principiul inducției matematice.

Soluția 1. Pentru n = 1,2 inegalitatea se verifică.

Presupunem că inegalitatea este adevărată pentru ni numere pozitive (i = 1, 2, …, n-l) și să demonstrăm că ea rămâne adevărată și pentru n numere pozitive a1,…,an.

Conform ipotezei de inducție putem scrie ≥(n-1)și

an+ ≥ (n-1)

Adunând cele două inegalități membru cu membru obținem:

+ (n-2) ≥ (n-1)[ +]

Însă

+≥ 2=

2,

astfel că + (n-2) ≥ 2∙(n-1)∙ ≥ n ∙

Soluția 2. Se demonstrează destul de ușor că inegalitatea este adevărată pentru un număr n de forma 2k (kN), folosind inducția matematică după k .

Fie acum nN iar k cel mai mic număr natural pentru care n 2k .

Numerele a1,a2,…an, , unde g = sunt pozitive și în număr de 2k.

Putem scrie deci

Însă = gn ∙ g2- n = g2

Obținem deci inegalitatea g, care este echivalenta în

final cu a1 + a2 +… + an n ∙ g = n ∙ .

2.5. Principiul includerii și excuderii

Vom prezenta în continuare un rezultat cunoscut sub numele de principiul includerii și excluderii:

Teorema 2.5.1. Fie M o mulțime finită iar M1, M2,…, Mn submulțimi ale lui M. Dacă pentru o mulțime M notăm prin |M| cardinalul său, atunci:

= – + – … +(-1)n-1

Demonstrație. Facem inducție matematică după n. Pentru n=l egalitatea din enunț

se reduce la |M1|=|M1|, ceea ce este evident. Pentru n=2 trebuie demonstrată egalitatea :

(1) |M1 M2|=|M1|+|M2|-|M1 M2|

care de asemenea este adevărată, deoarece elementele din M1 M2 apar atât la M1 cât și la M2.

Presupunem egalitatea din enunț adevărată pentru oricare m submulțimi ale lui M cu m<n și o să o demonstrăm pentru n submulțimi M1, M2,…. Mn.

Dacă notăm N = , atunci conform relației (1) putem scrie:

(2) = = + – .

Însă =() Mn = , deci aplicând ipoteza de inducție

pentru și ținând seama de faptul că ()()=()Mn , ()()()=(Mk)Mn etc, obținem:

(3) == – +- … +(-1)n-2.

Aplicând ipoteza de inducție și pentru |N| obținem:

(4) |N| = =- +- … +(-1)n-2 și ținând cont de (3) și (4) relația (2) devine:

= + – = () – () +

(+) – … +(-1)n-2 – (-1)n-3 + (-1)n-2= – +- … +(-1)n-1.

Conform principiului inducției matematice, egalitatea din enunț este adevărată pentru orice număr natural n nenul.

Aplicație

Câte numere naturale nenule mai mici sau egale cu 1000 sunt divizibile sau cu 2 cu 3 sau cu 5?

Soluție. Fie A = {2n : nN, 2n 1000}, B = {3n : nN, 3n 1000} și C = {5n : nN, 5n 1000} .

Se observă că AB = {6n : nN, 6n 1000},

AC = {10n: nN, 10n1000},

BC = {15n: nN, 15n1000},

ABC = {30n : nN, 30n 1000}.

Evident numărul căutat este |A B C|. Aplicând principiul includerii și excluderii pentru n = 3, avem |A B C|= |A| + |B| + |C|-|AB|-|AC|-|BC| + | ABC | =

++–+=

500+333+200-166-100-66+33=734.

Capitolul III

Aplicații ale principiilor de rezolvare a problemelor de matematică

Să se arate că orice număr natural n admite multiplii la a căror scriere în sistemul zecimal apar numai cifrele 0 și 1.

Să se afle mulțimea numerelor naturale n cu proprietatea: mulțimea {n, n+1, n+2, n+3, n+4, n+5} poate fi împărțită în două submulțimi disjuncte astfel încât produsul tuturor elementelor uneia din ele să fie egal cu produsul elementelor celeilalte submulțimi.

Fie ABCD un pătrat de latură 1 în interiorul căruia se trasează cercuri astfel încât suma perimetrelor lor să fie egală cu 10. Să se arate că există o infinitate de drepte cu proprietatea că fiecare intersectează cel puțin patru cercuri.

Fie P un pătrat de latură a și A, B două mulțimi în plan astfel încât PAB. Atunci A sau B au diametrul mai mare sau egal cu și este cel mai mic număr cu această proprietate.

Pe o sferă de rază 1 se iau la întâmplare 9 puncte. Demonstrați că există două puncte a căror distanță în linie dreaptă nu depășește .

O placă în formă de pătrat cu latura 1 este colorată cu trei culori. Să se arate că există două puncte la fel colorate a căror distanță este cel puțin .

Fie un pătrat cu latura de 38 cm și în interiorul său 100 de poligoane convexe de arie cel mult π cm2 și perimetru cel mult de 2 π cm. Să se arate că se poate trasa în interiorul pătratului un cerc de rază 1 cm care să nu taie nici unul dintre aceste poligoane.

Fie în plan un cerc de rază n (cu nN). Pe el se consideră m coarde cu proprietatea că orice punct din interiorul cercului este la distanță mai mică sau egală cu 1 de una din coarde. Să se arate că m n.

Dacă un determinant de ordinul n are n2 – n + 2 elemente egale, atunci determinantul este nul.

Se dau n numere naturale nenule distincte, toate mai mici decât 2n. Să se demonstreze că printre ele există unul egal cu n sau două a căror sumă este 2n.

(D. Miheț)

Se consideră un sistem de p ecuații cu q = 2p necunoscute:

în care fíecare coefícient aij{-l,0,l}.

Să se arate că există o soluție (x1,…,xq) a sistemului astfel încât:

toți xj (j = 1,2,…. q) sunt întregi;

Pentru cel puțin un j se găsește xj 0;

|xj|< p, pentru toți j = 1,2,…, q.

Fie aR* astfel încât a + Z. Atunci pentru orice nN, an+Z.

(L. Tuțescu)

Să se arate că dacă x1 a1 1, x2 a2 1,…, xn an 1, atunci

(V. Postolică)

Se consideră 2n numere reale x1 x2 …. xn și y1 y2 …. yn , nN. Fie z1 ,z2,.., zn o permutare a numerelor y1, y2,.., yn.

Să se demonstreze că

(OIM-1975)

3.15. Fie a1, a2, .., an numere reale astfel încât a1 cosx + a2 cos2x+… + an cosnx0, pentru orice xR. Atunci a1 cosx + a2 cos2x+… + an cosnx=0, pentru orice xR

(D. Bușneag)

Să se arate că orice polinom de grad n de o variabilă cu coeficienți strict pozitivi poate fi scris ca sumă de +1 polinoame cu coeficienți strict pozitivi și rădăcini strict negative.

(D. Ștefănescu)

Fie a > 0, a1 = a și an+1 = (an + ), pentru orice n 1.

Să se demonstreze că 2, pentru orice n 1

Să se demonstreze că pentru orice număr natural n 4 există un poligon convex cu n laturi, nu toate egale, astfel încât suma distanțelor de Ia orice punct interior la laturi să fie aceeași.

(D. Schwartz)

3.19 Se consideră pe o dreaptă n intervale cu proprietatea că oricare două au intersecția nevidă. Să se arate că toate intervalele au un punct comun.

Fie în plan două mulțimi de puncte finite și disjuncte. Să se arate că există o linie frântă închisă care nu se autointersectează, cu segmentele consecutive perpendiculare, care separă punctele celor două mulțimi.

(S.Popa)

3.21 Să se demonstreze că pentru orice număr natural m, există o mulțime E finită nevidă de puncte în plan cu proprietatea: Dacă AE, există în E, m și numai m puncte situate la distanța 1 de A.

(OIM)

Fie p un număr prim, p>2, iar x1, x2,.., xp-1_numere întregi, niciunul dintre ele nefiind divizibil prin p. Să se arate că cel puțin unul dintre numerele

e1x1 + e2x2 +…+ ep-1xp-1 (ei =±1) se divide cu p.

Să se demonstreze că dacă este un număr real astfel încât

cos =, atunci este irațional (unghiul ).

Câte numere naturale mai mici sau egale cu 1000 nu se divid nici cu 2 nici cu 3 nici cu 5?

Să se afle în câte moduri se pot împărți 5 obiecte distincte la 3 persoane, cu condiția ca fiecare persoană să primească cel puțin un obiect.

Fiind date n puncte în plan care se unesc între ele prin segmente, sâ se demonstreze că dacă nu există nici un triunghi cu vârfurile în cele n puncte, atunci există cel puțin un punct care este extremitatea a cel mult segmente.

Să se demonstreze că n puncte situate în plan pot fi unite prin cel mult segmente de dreaptă, astfel încât să nu se formeze nici un triunghi cu vârfurile în aceste puncte.

Fie n un număr natural. Folosind principiul includerii și excluderii să se găsească o formulă pentru determinarea lui (n), fiind indicatorul lui Euler.

Fie n un număr natural iar o permutare a mulțimii {1, 2, .., n}. Spunem că permutarea admite o coincidență în i dacă (i) = i.

Să se găsească numărul P(n) al permutărilor de n obiecte fără coincidențe.

Soluții

3.1. Considerăm numerele ak = cu 1 k n+1, adică a1 = 1,

a2 = 11, a3 =111, … Conform principiului lui Dirichlet, există 1 k < t n+1, astfel încât at = ak (mod n) , adică at – ak =pn, cu p N.

Astfel multiplul lui at – ak = are în scrierea sa numai cifrele 0 și 1.

(i) Printre cele șase numere ale mulțimii {n, n+1, n+2, n+3, n+4, n+5} există cel puțin un multiplu de 5. Dacă ar exista numai unul, partiția cerută nu se poate face, căci unul din produse ar avea pe 5 ca factor, iar celălalt nu. Deci trebuie să existe doi multipli de 5, ceea ce este posibil doar pentru n și n+5, care trebuie deci să facă parte din produse diferite și n = M5.

Avem n(n+l)(n+2)(n+3)(n+4)>(n+5), deci cu atât mai mult și (n+l)(n+2)(n+3)(n+4)(n+5)>5,

Avem n(n+l)(n+2)(n+3)>(n+4)(n+5) pentru n = 5, 10, 15, și cu atât mai mult alte combinații, cu n+4 la stânga.

Avem n(n+3)(n+4)<(n+l)(n+2)(n+5) și cu atât mai mult pentru alte combinații, cu n+1 sau n+2 la stânga.

În concluzie, pentru toate posibilitătile de partiție, produsele nu pot fî egale, oricare ar fi n N.

Fie C1, C2,…, Cn cele n cercuri înscrise în ABCD cu Ck de diametru dk (evident dk 1).

Prin ipoteză, = 10 deci = < n și deci n 4.

Să proiectăm C1, C2, …, Cn pe aceiași latură a pătratului, spre exemplu pe AB. Proiecția lui Ck pe AB este un interval Ik de lungime dk. Cum >3 și

0 < dk <1, rezultă imediat că cel puțin patru dintre intervalele I1,I2, …, In, de exemplu, I1,I2,I3,I4, se intersectează după un interval I de lungime pozitivă.

Atunci fiecare dreaptă paralelă cu latura AD care trece printr-un punct de pe I intersectează cel puțin cercurile C1, C2, C3 și C4 . Evident există o infinitate de astfel de drepte.

Evident una dintre cele două mulțimi, spre exemplu A, conține cel puțin două vârfuri consecutive ale lui P. Dacă A conține trei vârfuri ale lui P, atunci diam(A) diam(P) = a . Dacă A conține numai două vârfuri consecutive ale lui P, fie ele V1 și V2, atunci B conține celelalte două vârfuri V3 și V4 (vezi Fig.3). Cum M, mijlocul segmentului V1V4, aparține lui A sau lui B, rezultă că diam(A) sau diam(B) .

Se împarte sfera în opt regiuni egale prin trei plane perpendiculare două câte două trecând prin centru. Conform principiului lui Dirichlet există cel puțin două puncte în aceeași regiune.

Evident, distanța dintre ele nu poate depăși .

Dacă două vârfuri opuse ale pătratului sunt la fel colorate, problema este rezolvată.

Fie a, b, c cele trei culori.

În cazul în care două vârfuri ale pătratului nu sunt colorate la fel, se analizează cazurile:

(i) Nici un vârf nu este colorat cu culoarea c;

(ii) Două vârfuri alăturate sunt colorate cu culoarea a, unul cu b și unul cu c;

(i) Fie A, B, C, D vârfurile pătratului.

Să presupunem că vârfurile A și D sunt colorate cu culoarea a iar vârfurile B și C sunt colorate cu culoarea b (vezi Fig.4).

Fig.4

Alegem în acest caz punctele M și N pe DC și respectiv AB, astfel încât AN =, DM = (pătratul are latura egală cu unitatea).

Dacă M este colorat cu a avem: AM = >

Dacă M este colorat cu b avem: BM =>

Dacă N este colorat cu a avem: DN =>

Dacă N este colorat cu b avem: CN = >

Dacă M și N sunt colorate cu c avem: MN = >

(ii) Să presupunem că vârfurile A și D sunt colorate cu culoarea a, vârful B cu culoarea b iar vârful C cu culoarea c.

Fie N AB, M BC, N' CD astfel încât AN = , BM = , DN' .

Dacă M este colorat cu a avem: AM = >.

Dacă M este colorat cu b se analizează situațiile în care poate fi colorat N.

Dacă N este colorat cu a avem: DN=.

Dacă N este colorat cu b avem : MN=

Dacă N este colorat cu c avem: CN=.

Dacă M este colorat cu c se înlocuiește N cu N’(vezi Fig.5).

3.7 Se observă faptul că locul geometric al punctelor situate Ia o distanță mai mică de 1 cm de un poligon convex este un poligon cu laturile paralele poligonului dat și la distanța 1 cm de acestea, cu vârfurile rotunjite ca în Fig.6

Dacă notăm cu Pi poligoanele din figură și cu Qi locurile geometrice asociate, ca mai sus, i = 1, 2,…, 100, avem:

SQ= SP+(perimetrul lui Pi) + ,

deoarece coroanele se completează la un cerc cu raza 1 cm. Deci, SQ + 2 + = 4.

Deci poligoanele rotunjite Qi, nu pot, conform principiului lui Dirichlet, să acopere pătratul de latură 36 cm, dus în interiorul pătratului dat, cu laturile paralele cu ale acestuia și la distanță de 1 cm față de ele. Oricare dintre punctele neacoperite poate fi ales ca centrul cercului cerut.

3.8 Se observă că problema revine la a arăta că dacă benzile de lățime 2 constituite pe coardele respective acoperă cercul dat, atunci m n. Din păcate nu putem face o apreciere a ariei unei astfel de benzi pentru a aplica direct principiul lui Dirichlet.

Vom face următoarea construcție auxiliară: ducem sfera de rază n cu același centru O ca și cercul.

Tăiem sfera prin două plane perpendiculare pe planul cercului și paralele la una dintre coarde AkBk și la distanța 1 de aceasta (vezi Fig.8).

Fig.8

Aria din sferă cuprinsă între cele două plane va fl Sk 2 2n 4n. Repetând construcția pentru k = 1, 2,…, m și aplicând principiul lui Dirichlet,

42 4m.

Orice determinant de ordinul n are n2 elemente așezate astfel: n elemente pe diagonala pricipală și elemente așezate de fiecare parte a diagonalei principale.

Dacă n2 – n + 2 elemente sunt egale, atunci n-2 elemente diferă de valoarea comună a celor egale. Aceste n-2 elemente pot fi repartizate în cel mult n-2 linii sau coloane. Deci rămân două linii sau coloane identice, ceea ce implică faptul că determinantul este nul.

Fie x1,x2,…,xn numerele din enunț.

Evident și 2n – x1, 2n – x2,…, 2n – xn au aceleași proprietăți.

Numerele x1,x2,…,xn ,2n – x1, 2n – x2,…, 2n – xn, nu pot fi toate distincte deoarece în intervalul (0, 2n) există numai 2n-1 numere naturale distincte. Deci există i,j {1,2,…, n} astfel încât ai = 2n – aj, de unde deducem că ai=n dacă i=j, sau ai + aj = 2n dacă i j.

Se consideră q-uplurile (x1, x2, …, xq) în care xj Z, j = 1,..,q, cu

proprietatea p este ales în 2p+l moduri.

Avem inegalitatea qp pentru un astfel de sistem de q numere. Deci numărul sistemelor posibile (a11xI+…+a1qxq, …,

ap1 x1+…+apqxq) care corespund q-uplurilor (x1, x2, …, xq) considerate nu depășește 2pq+l.

Cum (2pq+l)p < (2p+l)q, deducem că există două sisteme distincte (, ,…,), (, ,…, ) de numere cu proprietățile amintite astfel încât

ai1…+ aiq = ai1…+ aiq pentru i = 1,2, …,p.

Notând xi=, i = 1,…, q, găsim soluția sistemului pe care o căutăm.

Scriind că (a + )(+ ) = (+ )+(+ )

și totul rezultă făcând inducție matematică după nN.

Dacă n = – m Z , cu mN avem că + = +Z conform celor

demonstrate anterior.

Pentru n = 1 inegalitatea devine =1, adică a1 1, ceea ce este adevărat. Presupunând inegalitatea adevărată pentru n, vom demonstra că ea este adevărată și pentru n+1; aceasta revine la a arăta că

Din ipoteză avem că

înmulțind ambii membrii ai acestei inegalității cu l+an+1 obținem

Este suficient să demonstrăm că

Din enunț avem că x1 a1 1, x2 a2 1,…, xn an 1 , ceea ce implică >0,…,>0.

Prin urmare inegalitatea anterioară este echivalentă cu

+ +

()

Această ultimă inegalitate este echivalentă, pentru > 1, cu

Din x1 a1 1, x2 a2 1,…, xn an 1 obținem

Conform principiului inducției matematice inegalitatea cerută este adevărată pentru orice nN.

Tratăm la început cazul n = 2 care revine la x1y1 +x2y2 x1y2 + x2y1 (x1-x2) (y1-y2), ceea ce este adevărat.

Să presupunem inegalitatea adevărată pentru n-1.

Dacă y1=z1 atunci ea se reduce la , care este adevărată conform ipotezei de inducție, deoarece z2, …, zn reprezintă în acest caz o permutare a lui y2,…,yn.

Dacă y1=zj cu j 1; atunci conform cazului n = 2 avem

= (x1 – z1)2 +(xj – zj)2 + (x1 – y1)2 +(xj – z1)2 +

Pe baza ipotezei de inducție și a faptului că z2,…,zj-1,z1,zj+1,…,zn este o permutare a lui y2,.., yn deducem că (xj – z1)2 + . ceea ce încheie trecerea de la n-1 la n. Conform principiului inducției matematice inegalitatea este adevărată pentru orice nN.

Soluția 1. Fie P(n) propoziția din enunț.

Dacă n = 1 și a1 cos x 0, pentru orice x R, atunci cu necesitate a1 = 0 și deci a1 cos x = 0, pentru orice x R. Deci P(1) este adevărată.

Să presupunem acum că P(k) este adevărată pentru orice k n-1, kN, și să demonstrăm că în această ipoteză rezultă și P(n) adevărată.

Avem deci a1cosx + a2cos2x+…+ancosnx 0, pentru orice x R.

Dacă în (1) facem substituția x x+ atunci (1) devine,

–a1 cosx + a2 cos2x – a3 cos3x+… + (-l)nancosnx0, pentru orice x R.

Să presupunem că n este par (analog se tratează și cazul n impar).

Din (1) și (2), prin sumare rezultă

2a2 cos2x+2a4 cos4x+…+2an cosnx 0, pentru orice x R, deci

a2 cos2x+ a4 cos4x+…+ an cosnx 0, pentru orice x R.

Dacă în (3) substituim 2x = y, obținem că

a2 cosy+ a4 cos2y+…+ an cos(y) 0, pentru orice y R.

Aplicând ipoteza de inducție (k=) rezultă că

a2 cosy+ a4 cos2y+…+ an cos(y) = 0,pentru orice y R

a2 cos2x+ a4 cos4x+…+ an cosnx 0, pentru orice x R.

Astfel (1) devine

a1 cosx+ a3 cos3x+…+ an-1 cos(n-1)x, pentru orice x R.

Dacă în (5) înlocuim pe x cu x+ obținem

-a1 cosx – a3 cos3x-…- an-1 cos(n-1)x, pentru orice x R

a1 cosx+ a3 cos3x+…+ an-1 cos(n-1)x 0, pentru orice x R .

Ținând cont de (5) și (6) deducem că

(7) a1 cosx+ a3 cos3x+…+ an-1 cos(n-1)x 0, pentru orice x R.

Ținând cont de (4) și (7) deducem că a1 cosx + a2 cos2x+… + an cosnx=0, pentru orice xR, adică P(n) este adevărată pentru orice n N.

Soluția 2. Considerăm funcțiile f, F : R R

f(x)= a1 cosx + a2 cos2x+… + an cosnx și F(x)= a1 sinx + sin 2x +…+ sin nx

Evident F este o primitivă a funcției f și F(k) = 0, pentru orice kZ.

Cum F'(x) = f(x) 0, pentru orice x R deducem că F crescătoare. Deoarece F este și periodică rezultă că F este constantă. Ținând cont că F(k) = 0, pentru orice kZ deducem F(x) = 0, pentru orice x R. Atunci și F'(x) = 0, adică f(x) = 0 pentru orice x R.

Pentru n = 1,2 problema rezultă imediat.

Dacă P(x) este un polinom de grad n natunci există două numere a și b pozitive, convenabil alese, astfel încât P(x)=(x+a)n-1(x+b)+Q(x), unde Q(x) este un polinom de grad n – 2 și are coeficienți pozitivi. Ținând cont de acestea, realizăm trecerea de la n la n+2. Cum pentru n =1,2 afirmația este adevărată, ea va fi adevărată pentru orice valoare a lui n.

Pentru n = 1 relația este evident adevărată.

Să presupunem că (1) = ( )

Atunci (2) = = = ( )

Ținând cont de (1), (2) devine = [( )] 2 = ( )

Conform principiuhn inducției matematice relația (1) este adevărată pentru orice n

Să considerăm la început un poligon convex cu n laturi care satisface condiția din enunț.

Considerăm în plan o direcție neparalelă cu nici una din laturi și tăiem după această direcție două vârfuri ale poligonului astfel încât nici un alt vârf să nu fie îndepărtat în afara celor două (vezi Fig.9).

Obținem astfel un poligon convex cu n+2 laturi, nu toate egale (putem face tăieturile în acest fel). În plus, suma distanțelor unui punct interior la laturile vechiului poligon (care este constantă) plus suma distanțelor la cele două laturi nou apărute, care însă sunt paralele, iar punctul este situate între ele, deci și această sumă este constantă (egală cu distanța dintre cele două laturi). Am arătat deci cum se face trecerea de la n la n+2.

Trecerea la 5 se face pornind de la un triunghi ehilateral, iar pentru 4 dispunem de dreptunghi (triunghiul echilateral și dreptunghiul au proprietatea cerută – vezi Fig. 10, 11).

Pentru n = 2, totul este evident. Fie acum n intervale cu proprietatea din enunț și să notăm cu T intersecția a n-1 intervale (T este un interval) și conform pasului de inducție T. Să notăm cu Tn al n-lea interval și să presupunem că T Tn= .

Fie A0Tn punctul cel mai apropiat de T.

Deoarece A0T, există ITn un interval din mulțimea considerată astfel încât A0 I . Pe de altă parte IT și ITn. Fie A1 IT și A2 ITn. Atunci segmentul A1 A2 I, dar A0 A1 A2 (căci în caz contrar A2 ar fi mai aproape de T decât A0), ceea ce este contradictoriu (căci ar rezulta A0 I).

Pentru n = 1, 2 totul este clar. Trecerea de la n la n+1 se face unind convenabil cel de-al n+1 lea punct cu unul din vârfurile liniei frânte construită pentru mulțimea cu n puncte, urmând ca apoi să se realizeze în jurul drumului considerat, linia frântă cerută.

Propoziția din enunț este adevărată pentru n = 1, luând două puncte din plan la distanța 1.

Să presupunem că există o mulțime E, având de exemplu k elemente și care satisfac condițiile problemei pentru un m oarecare.

Considerăm o mulțime E' definită prin translația lui E într-o anumită direcție cu modulul 1. Există cel mult km direcții de translație pentru care două puncte din E și E' pot coincide; putem alege deci o direcție pentru care punctele lui E și E' să fie toate distincte.

Orice punct din E se află la distanța 1 de omologul său din E'; există atunci cel mult 2(k-l) direcții de translație prin care un punct din E ar putea ajunge la distanța 1 de un punct neomolog (căci cercurile de rază 1 cu centrele în cele două puncte au cel mult două puncte de intersecție). În total putem avea 2k(k-l) astfel de direcții; putem alege din infinitatea de direcții de translație, una pentru care acest lucru să nu se întâmple.

În acest caz reuniunea lui E cu E' are proprietatea că orice punct are exact m+1 puncte din mulțime (m din ipoteza inducției și un punct analog) la distanța 1.

Am arătat deci că P(m) P(m+l) și cum P(1) este adevărată atunci P(m) este adevărată pentru orice m N.

1) Să demonstrăm mai întâi că dacă x1, x2, .., xp-1 sunt numere întregi nedivizibile prin p (p prim, p> 2), iar S1, S2,.., Sm sunt sumele elementelor grupărilor ce se pot forma cu aceste numere în toate modurile posibile, atunci oricare ar fi r {1,2,…, p-1} există i {1,2,…, m} astfel încât S1 r(mod p) .

(i). Pentru a dovedi afirmația de mai înainte, demonstrăm prin inducție completă că dacă x1, x2,.., xk sunt numere întregi nedivizibile cu p, atunci dintre numerele S1,S2, .., Sr putem extrage k numere care prin împărțire la p, să dea k resturi diferite și diferite de 0, unde 0<kp-l.

Pentru k = 1 verificarea este imediată.

Presupunem afirmația adevărată pentru k, 0 < k < p-1 și o probăm pentru k+1.

Aceasta înseamnă că din numerele x1, x2, .., xk, xk+1 putem forma k grupări astfel încât sumele elementelor lor să dea k resturi diferite și diferite de 0 la împărțirea prin p; fie acestea y1, y2,…, yk.

Presupunem că nu mai există un alt grup astfel încât suma elementelor sale să dea la împărțirea prin p un rest diferit de y1, y2, .., yk și diferit de 0. Se știe însă că dacă p este prim, și xN nu este divizibil prin p, atunci numerele 1, x, 2x, …, (p-1)x dau la împărțirea prin p resturile 1, 2, ,,., p-1 (nu neapărat în această ordine). Din acest motiv există numerele a1,a2,..,ak{l,2,…,p-l} astfel încât ai xk+i =yi (mod p) .

Dar xk+1 dă la împărțirea prin p unul din resturile y1, y2, .., yk (în caz contrar s-ar contrazice ipoteza); fie acesta y1, deci xk+1=y1 (mod p), adică a1=l.

Putem presupune a1 < a2 <… <ak și vom arăta că ai + 1= ai+1.

Într-adevăr, dacă ai + 1 ai+1, considerând grupul format din xk+1 și grupul al cărui rest rezultat prin împărțirea la p a sumei elementelor sale este yi, atunci suma elementelor sale va da la împărțirea prin p același rest ca și numărul (ai + l)xk+1 și cum a1< a2 <…< ai-1 < ai + 1< ai+1 rezultă că restul obținut va fi diferit de y1, y2,.., yk și diferit de 0; absurd. Dar cum a1 = 1, a2 = 2, …, ak = k, considerând grupul format din xk+1 și grupul a cărui sumă a elementelor dă restul yk la împărțirea prin p, restul dat la împărțirea prin p de suma elementelor iui va fi același cu restul dat la împărțirea prin p de numărul (ak + l)xk+1, deci de numărul (k+ l)xk+1, care va fi diferit de y1, y2,.., yk și diferit de 0 (k+l<p), contradicție.

Deci, cu numerele x1, x2,.., xk, xk+1 se pot forma k+1 grupări, k < p-1, astfel încât sumele elementelor lor la împărțirea prin p să dea k+1 resturi diferite de 0, adică tocmai ceea ce trebuia probat.

Proprietatea de la punctual 1) decurge din cele arătate la punctul 2).

3) Vom distinge două situații:

dacă x1 + x2 +…+ xp-1 este divizibil prin p exercițiul este rezolvat.

dacă x1+ x2 +…+ xp-1 r (mod p), 0 < r p-1 atunci conform proprietății 1) cu numerele 2×1, 2×2, .., 2xp-1 putem forma o grupare (2x, 2x ,…, 2x ), astfel încât 2x+ 2x + …+ 2x r (mod p). Atunci numărul = x1 + x2 + …+ xp-1 – (2x+ 2x + …+ 2x) va fi divizibil prin p, și cum x este de forma e1x1 + e2x2 +… + ep-1xp-i (ei =±1), problema este rezolvată.

Funcția cos(k), cu = Q, dat, (m, n Z și n > 0) ia cel mult 2n valori distincte când k Z . Pentru a ne convinge de acest lucru este suficient să ne amintim că rădăcinile ecuației x2n -1 = 0, care sunt exact în număr de 2n, sunt date de relația xk =cos + i sin, k = 0, 1, 2, …, 2n-l, și că pentru orice valoare a lui k, în afară de cele arătate mai sus, nu obținem numere xk distincte de rădăcinile ecuației.

Vom arăta prin inducție că cos(t), atunci când, t = 2k, k = 1, 2, … ia o infinitate de valori distincte și de aici rezultă iraționalitatea lui .

În acest scop folosim identitatea cos2x = 2cos2 x-1. Cu x = , avem

cos(2) = 2 – 1 = -1, cu 2 care nu se divide în mod evident cu 3. În continuare scriem cos(22)=2cos2(2) – 1= 2( -1 )2 – 1 = – 1, cu 98 care nu se divide la 3. Să presupunem acum că cos(2k)=, cu r nedivizibil la 3 și să arătăm că cos(2k+1)= -1, cu s nedivizibil la 3.

Într- adevăr cos(2k+1) = 2 cos2 (2 k ) -1 = 2 – 1 = = – 1, unde s = .

Evident dacă r nu se divide la 3, nici s nu se divide la 3, căci r2 nu se divide la 3. Rezultă deci că relația cos(2k ) =- 1, cu r3p, pZ, este adevărată pentru orice kN și astfel cos(2k ) nu ia un număr finit de valori (anume 2n valori ca în cazul = Q), ci o mulțime infinită de valori distincte două câte două.

Deci Q , de unde rezultă că \Q

Cum 734 de numere se divid fie cu 2, fie cu 3, fie cu 5 (conform aplicației 1 de la Capitolul 6, paragraful 6.3), 1000-734=266 nu se divid nici cu 2, nici cu 3, nici cu 5.

Numărul căutat este egal cu numărul funcțiilor surjective definite pe o mulțime cu 5 elemente cu valori într-o mulțime cu 3 elemente, deci este egal cu S5,3 = 35 -C 25 + C = 150 (vezi Propoziția 7.1.11, (iv)) .

Într-adevăr, pentru un punct notat x, fie Ax mulțimea punctelor legate cu x

printr-un segment și să presupunem prin absurd că +1, pentru orice x X, unde cu X am notat mulțimea celor n puncte din plan.

Să alegem un punct x1 X și în mulțimea A să alegem un punct y1.

Avem = |A | +|A | – 2+ 2 – n, deoarece |X| = n. Dar 2+ 2 – n = 2 +1 – n +1 1, deci există z1 , această mulțime conținând cel puțin un element. Am ajuns însă la o contradicție, deoarece x1, y1, z1 sunt vârfurile unui triunghi iar noi am presupus că nu există nici un triunghi cu vârfurile în punctele din X.

Deci există un punct x X astfel încât |Ax | ≤ .

Vom demonstra problema prin inducție după n.

Pentru n = 1 sau n = 2 rezultatul este imediat, deoarece în primul caz numărul segmentelor este egal cu zero, iar în al doilea caz este egal cu 1.

Să presupunem problema adevărată pentru n puncte și să o demonstrăm pentru n+1puncte.

Știm că există un punct x X cu |X|= n+1 care este extremitatea a cel mult segmente, conform exercițiului 6.26. Dar mulțimea de puncte X \ {x} poate fi unită prin cel mult segmente astfel încât să nu se formeze nici un triunghi cu vârfurile în aceste puncte, deci numărul total de segmente care unesc punctele din mulțimea X (cu n+1 puncte) este majorat de +.

Vom demonstra că acest număr este egal cu .

Într-adevăr fie n=2k, cu k N.

Atunci +=k + k2=, deoarece

= = =k(k+1).

Dacă n=2k+1, cu kN, atunci += k+1 + = k+1+k(k+1) = (k+1)2 = .

Deci, am arătat că +=și cu aceasta demonstrația este încheiată.

Observație. Pentru a obține exact segmente de dreaptă între cele n puncte astfel încât să nu se formeze nici un triunghi cu vârfurile în aceste puncte, se poate proceda astfel : se grupează cele n puncte în două clase care conțin respectiv și n – puncte și se unește fiecare punct cu toate punctele care nu aparțin aceleiași clase cu el.

3.28 Să scriem descompunerea lui n în factori primi n = p p… pși să notăm cu Ai mulțimea numerelor naturale mai mici sau egale cu n care sunt multipli de pi (i = 1,2, … ,q, q N).

Avem = , = , ș.a.m.d.

Pentru a obține numărul numerelor naturale mai mici sau egale cu n și care sunt prime cu n, trebuie să scădem din numărul numerelor naturale mai mici sau egale cu n , numărul numerelor mai mici sau egale cu n care nu sunt prime cu n, adică aparțin mulțimii A1 A2 … Aq.

Deci = n –

= n –

Dând factor comun pe n, obținem

= n.

3.29 Să notăm cu A mulțimea celor (n-l)! permutări care admit o coincidență în i șj să aplicăm principiul includerii și excluderii pentru a găsi numărul permutărilor care admit cel puțin o coincidență.

Acest număr este egal cu =- (-1)n-1.

Dar = (n-k)! . Pe de altă parte, k poziții i1, i2, …, ik pot fi alese din mulțimea celor n poziții în C moduri.

Deoi = C (n- 1)! – C (n- 2)!+… + (-1)n-1 C.

Numărul permutărilor de n obieete fără coincidențe se obține scăzând din numărul tuturor permutărilor, care este egal cu n!, numărul permutărilor care admit măcar o coincidență. Deci P(n) = n! – C (n- 1)! + C (n- 2)!-… + (-1)n-1

C.