Browse · MathNet
PrintXIV 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.
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