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$
Problem
Source: CWMO 2012 Q3
Tags: combinatorics proposed, combinatorics
02.10.2012 09:13
fallow math_explorer's proof in this link:(from where he has said : We can see that this means ...) http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2534625&sid=b82b1dc6685401935cd440d610e7cc8f#p2534625 thus he has proved that the maximum number of non-empty subsets from $\left \{ 1,...,n \right \}$ that satisfy the above condition is $2n-1$ so if we add empty-set to them we have a family of $2n$ subsets from $\left \{ 1,...,n \right \}$ with the problem's property so the answer is $2n$
24.07.2014 21:16
If we count full set to also be a subset and we don't count empty subset which is the most logical to me answer is $2n-1$.We prove this by quite easy strong induction.Cases $n=1$ and $n=2$ are trivial.Now suposse this hold for every $n=\left\{ 1,...,n-1\right\}$.Now let $k,k \not= n $ be the largest cardinality of a subset of $A$($k>[\frac{n+1}{2}]$ because if it was otherwise we would be easily able to prove that maximum in this case is less than maximum when $k>[\frac{n+1}{2}]$ ).Let the elements of that subset be k-elements and the other be 'other' elements.Now as this k-subset can't be contained in any other subset we obtain that there is no subset that contains both one of the k-elements and one of the 'other' elements.So now basicaly we have $2$ separate sets.Maximum number of subsets in k-subset that contain the task are $2k-1$ and in the other subset it is $2(n-k)-1$.We also didn't count the whole set so the answer is now $2k-1+2(n-k)-1+1=2n-1$ so we are finished.As for the example take: $\left\{a_1 \right\}, \left\{a_2\right\}, \cdots , \left\{a_n\right\}, \left\{a_1,a_2\right\} , \left\{a_1,a_2,a_3\right\}, \cdots , \left\{a_1,a_2,\cdots,a_n\right\}$.