Va rog,ajutati ma!!!!!
Răspunsuri la întrebare
► Cerinta
La o intalnire participa 7 persoane. Aratati ca exista cel putin doua persoane care sa aiba acelasi numar de prieteni la aceasta intalnire.
(Aratati ca nu este posibil ca participanti sa aiba toti un numar diferit de prieteni.)
► Metoda de rezolvare I :
Presupunere si aducere la absurd.
Rezolvare :
Presupunem ca la intalnire participa persoane care au numar diferit de prieteni.
Numarul maxim de prieteni pe care o persoana ii poate avea la aceasta intalnire este 6 (cazul in care cineva e prieten cu toti ceilalti participanti, nu ai cum sa ai mai multi prieteni participanti la intalnire decat numarul total de participanti).
Deci la aceasta intalnire poti avea 0,1,2,3,4,5 sau 6 prieteni prezenti (7 variante). Daca fiecare persoana din cele 7 are un numar diferit de prieteni atunci o persoana are 0 prieteni la intalnire, o persoana are 2 pieteni la intalnire, .... o persoana are 6 prieteni la intalnire (principiul porumbelului).
Daca o persoana are 6 prieteni care participa la intlnire atunci acea persoana este prietena cu toata lumea. Dar daca avem la intalnire si o persoana care are 0 prieteni atunci aceasta nu e prieten cu nimeni. Deoarece prietenia e o relatie bidirectionala am ajuns la o situatie imposibila, absurda. Deci afirmatia e falsa, e imposibil sa avem persoane cu numar diferit de prieteni.
► Metoda de rezolvare II :
Modelare cu teoria grafurilor.
Rezolvare :
Problema data poate fi modelata folosind un graf neorientat astfel :
- Nodurile grafului sunt persoanele prezente la intalnire
- Muchiile reprezinta relatia de prietenie. Gradul unui nod reprezinta numarul de prieteni prezenti la intalnire.
Presupunem ca nu exista doua persoane cu acelasi numar de prieteni. Gradul maxim al unui nod este egal cu numarul de noduri - 1 = 7-1 = 6. Deci avem un nod cu grad 0, unul cu grad 1, unul cu grad 2, ... unul cu grad 6 (principiul porumbelului).
Suma gradelor nodurilor este 0+1+2+3+4+5+6 = 21.
Stim ca intr-un graf neorientat suma gradelor trebuie sa fie un numar par. Observam ca 21 nu este un numar par, deci presupunerea este gresita.
► Concluzie :
La o intalnire cu 7 persoane trebuie sa existe cel putin doua persoane care au acelasi numar de prieteni.