Skip to main content
OlympiadHQ

Browse · MathNet

Print

XIV OBM

Brazil counting and probability

Problem

Given a set of elements, find the largest number of subsets such that no subset is contained in any other.
Solution
Let have elements. The number of sequences of chains such that is : for each permutation of elements from let .

Fix a subset of . If , then the chains containing is , because there are choices for and choices for . If and are such that and , then every pair of chains, one containing and other containing , are disjoint. So if are subsets such that and then, denoting , The maximum value of is . Hence

One example with is considering all subsets with elements.
Final answer
binomial(n, floor(n/2))

Techniques

Counting two waysColoring schemes, extremal arguments