MathDB

Disjoint or entirely contained subsets

Source: CWMO 2012 Q3

October 1, 2012

combinatorics proposedcombinatorics

Problem Statement

Let

A

be a set of

n

elements and

A_1, A_2, ... A_k

subsets of

A

such that for any

2

distinct subsets

A_i, A_j

either they are disjoint or one contains the other. Find the maximum value of

k