mateforum.ro

Demonstrati ca daca intr-o clasa se afla n elevi, \( n\ge 2 \),exista doi elevi care au acelasi numar de prieteni.
(Se presupune ca daca elevul x este prieten cu elevul y , atunci si y este prieten cu x, iar x nu poate fi prieten cu el insusi)

Numarul maxim de prieteni ce ii poate avea elevul A este n-1 ( toti elevii inafara de el insusi ). Totodata nr minim de prieteni ce ii poate avea elevul B este de 0. Demonstram ca nu pot exista in acelasi timp doi elevi A si B astfel incat A sa aiba n-1 prieteni si B sa nu aiba niciunul. Pp prin reducere la absurd ca asa ceva sa poate => A este prieten cu toti elevii din clasa mai putin cu el insusi => A este prieten cu B => B este prieten cu A . Contradictie cu faptul ca B nu are nici un prieten. => Presupunerea facuta este falsa =>Nu pot exista in acelasi timp doi elevi A si B astfel incat A sa aiba n-1 prieteni si B sa nu aiba niciunul. Deci nr de prieteni pe care ii pot avea elevii din clasa este n-1. (1 prieten, 2 prieteni,....,n-1 prieteni sau 0 prieteni,1 prieten..... n-2 prieteni ). Nr elevilor din este de n. => Cu principiul cutiei => ca Exista doi elevi care au acelasi numar de prieteni.

Soluta 2:
Presupunem prin absurd ca nu exista 2 elevi cu acelasi numar de prieteni: un elev va avea 0 prieteni, un elev 1 prieten , un elev 2 prieteni,...., ultimul elev n-1 prieteni, contradictie, deoarece ultimul elev ar fi prieten cu toti deci si cu primul elev.