30.03.2012 - combinatorica [cls VII-VIII]

mircea.lascu
Mesaje: 350
Membru din: Lun Iul 12, 2010 9:02 pm

30.03.2012 - combinatorica [cls VII-VIII]

Mesaj 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.
radu alberto
Mesaje: 89
Membru din: Joi Apr 04, 2013 4:38 pm

Re: 30.03.2012 - combinatorica [cls VII-VIII]

Mesaj 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.
Scrie răspuns