30.03.2012 - combinatorica [cls VII-VIII]

30.03.2012 - combinatorica [cls VII-VIII]

Mesajde mircea.lascu » Lun Mar 26, 2012 9:09 am

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.
mircea.lascu
 
Mesaje: 349
Membru din: Lun Iul 12, 2010 9:02 pm

Re: 30.03.2012 - combinatorica [cls VII-VIII]

Mesajde radu alberto » Mar Sep 10, 2013 8:01 am

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.
LE[unparseable or potentially dangerous latex formula]A:Fie A una dintre persoane si [unparseable or potentially dangerous latex formula][unparseable or potentially dangerous latex formula][unparseable or potentially dangerous latex formula]F_1,F_2...,F_k},lista prietenilor lui.Pentru orice A ,[unparseable or potentially dangerous latex formula] este par.
Demontratia  Lemei:Fie F_i o persoana aleasa aleator din [unparseable or potentially dangerous latex formula].Pentru fiecare persoana F_i consideram lista ei de prieteni in [unparseable or potentially dangerous latex formula].
Vom avea [unparseable or potentially dangerous latex formula] liste.Numarul total de prieteni din aceste [unparseable or potentially dangerous latex formula] liste este par deoarece este egal cu de doua ori numarul de cunoastinte din [unparseable or potentially dangerous latex formula]. Prin ipoteza numarul persoanelor din fiecare lista este impar, deci se obtine [unparseable or potentially dangerous latex formula] numar par,astfel lema este domonstrata.
Fie k=2m.Acum pentru orice persoana [unparseable or potentially dangerous latex formula]\in[unparseable or potentially dangerous latex formula] consideram lista de prieteni a acesteia care nu contine pe A,nu nu mai din [unparseable or potentially dangerous latex formula].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 [unparseable or potentially dangerous latex formula] liste ,prin uramre un numar par de prieteni in cele [unparseable or potentially dangerous latex formula] 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 [unparseable or potentially dangerous latex formula] persoane cu un numar par de prieteni comuni.
radu alberto
 
Mesaje: 89
Membru din: Joi Apr 04, 2013 4:38 pm


Înapoi la Problema zilei

Cine este conectat

Utilizatorii ce navighează pe acest forum: Niciun utilizator înregistrat şi 1 vizitator

cron