×

# Interesting combinatorics problem involving bijections

Question 1: How many subsets of $$U=\{ 1,2,...,50\}$$ *are there such that their elements' sum exceeds * $$637$$?

Solution: $$1+...+50=1275=638+637$$ Thus for each subset $$S$$ whose elements sum to more than $$637$$, there is another subset (namely $$\{1,...,50\} \setminus S$$, the set with all the elements of $$\{1,...,50\}$$ minus all the elements in $$S$$). There are $$2^{50}$$ subsets of $$\{1,...,50\}$$, so there are $$\boxed{2^{49}}$$ subsets that satisfy the property.

Question 2: How many subsets of $$U=\{ 1,2,...,n\}$$ are there such that their elements' sum exceeds * $$m$$ *, with $$m \le \frac{n(n+1)}{2}$$?

This question is significantly harder as the symmetry argument made in the first question won't hold in the majority of cases.

Note by A L
3 years, 9 months ago

Sort by: