C-Tabara MATHTIME-Jupiter.ziua5.ex3

C-Tabara MATHTIME-Jupiter.ziua5.ex3

Mesajde Iman » Sâm Sep 03, 2011 6:48 pm

Fie $ n $ \in \Bbb{N}.Gasiti numarul natural maxim $ k $ astfel incat putem selecta $ k $ submultimi diferite ale unei multimi cu $ n $ elemente,oricare $ 2 $ avand intersectia nevida.
Avatar utilizator
Iman
 
Mesaje: 51
Membru din: Mar Noi 16, 2010 9:51 pm
Localitate: Constanta

Re: C-Tabara MATHTIME-Jupiter.ziua5.ex3

Mesajde dangerous storm » Joi Mar 12, 2015 2:13 pm

Foarte cunoscuta problema.Raspunsul este 2^{n-1}.
Fie A o multime de n elemente.Impartim cele 2^n submultimi ale lui A in 2^{n-1} perechi de forma (X,A-X),unde X reprezinta o submultime a lui A.Daca am avea k>2^{n-1},atunci din principiul cuitiei ar exista doua submultimi din cele k care formeaza o pereche,contradictie!
dangerous storm
 
Mesaje: 145
Membru din: Joi Iul 03, 2014 9:29 pm


Înapoi la Combinatorica

Cine este conectat

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

cron