Pagina 1 din 1

30.03.2012 - combinatorica [cls VII-VIII]

Scris: 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]

Scris: 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.
$L$$E$$M$$A$: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$$\in$$M$ 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.