C-Tabara MATHTIME-Jupiter.ziua5.ex3
C-Tabara MATHTIME-Jupiter.ziua5.ex3
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.
-
dangerous storm
- Mesaje: 145
- Membru din: Joi Iul 03, 2014 9:29 pm
Re: C-Tabara MATHTIME-Jupiter.ziua5.ex3
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!
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!