Pagina 1 din 1

30.03.2012 - combinatorica [cls VII-VIII]

MesajScris: Lun Mar 26, 2012 9:09 am
de mircea.lascu
O clasa are un numar par de elevi. Aratati ca exista doi copii care au un numar par de prieteni comuni printre colegi. Consideram ca relatia de prietenie este simetrica.

Re: 30.03.2012 - combinatorica [cls VII-VIII]

MesajScris: Mar Sep 10, 2013 8:01 am
de radu alberto
Presupunem contrariul,ca fiecare pereche de elevi din S are un numar impar de prieteni comuni,unde S este multimea elevilor din clasa.Folosim urmatoarea lema.
LEMA:Fie A una dintre persoane si M={F_1,F_2...,F_k},lista prietenilor lui.Pentru orice A ,k este par.
Demontratia  Lemei:Fie F_i o persoana aleasa aleator din M.Pentru fiecare persoana F_i consideram lista ei de prieteni in M.
Vom avea k liste.Numarul total de prieteni din aceste k liste este par deoarece este egal cu de doua ori numarul de cunoastinte din M. Prin ipoteza numarul persoanelor din fiecare lista este impar, deci se obtine k numar par,astfel lema este domonstrata.
Fie k=2m.Acum pentru orice persoana F_j\inM consideram lista de prieteni a acesteia care nu contine pe A,nu nu mai din M.Din lema aplicata lui F_i obtinem ca fiecare kista contine un numar impar de prieteni (deoarece nu il mai contine pe A),iar in toatal avem 2m liste ,prin uramre un numar par de prieteni in cele 2m liste ,dar atunci cel putin una din cele 2m-1 persoane (exceptand pe A) apare intr-un numar par de liste,adica acea persoana are un numar par de de prieteni comuni cu A ,contradictie.
Aceasta contradictie incheie problema demonstrand ca exista 2 persoane cu un numar par de prieteni comuni.