Skip to main content
OlympiadHQ

Browse · MathNet

Print

China Girls' Mathematical Olympiad

China counting and probability

Problem

Let be an integer greater than two, and let be pairwise distinct nonempty subsets of . Determine the maximum value of . (Here, we set . For a set , let denote the number of elements in .)
Solution
The answer is .

We consider each summand . If is the empty set, then . If is nonempty, because , at least one of and has more than one element, that is, . Because is a subset of each of and , and It follows that This upper bound can be achieved with sets
Final answer
n

Techniques

Coloring schemes, extremal arguments