Question

Let $n$ be a natural number and $X=\{1,2,......,n\}$. For subsets $A$ and $B$ of $X,$ we denote $A\Delta B$ to be the set of all those elements of $X$ which belong to exactly one of $A$ and $B.$ Let $F$ be a collection of subsets of $X$ such that for any two distinct elements $A$ and $B$ in $F$, the set $A\Delta B$ has at least two elements. Show that $F$ has at most $2^{n-1}$ elements. Find all such collections $F$ with $2^{n-1}$ elements.

Answer 1

For each subset $A$ of $\{1,2,.....,n-1\}$, we pair it with $A\cup \left\{n\right\}$.
Note that for any such pair $(A,B)$ not both $A$ and $B$ can be in $F$.
Since there are $2^{n-1}$ such pairs it follows that F can have at most $2^{n-1}$ elements.
By induction $|F|=2^{n-1}$, then F contains either all the subsets with odd number of elements or all the subsets with even number of elements.
Suppose that the result is true for $n=m-1$.
Now consider $n=m$.
Let $F_1$ be the set of those elements in F which contain $m$ and $F_2$ be the set of those elements which do not contain $m$.
By induction, $F_2$ can have at most $2^{m-2}$ elements.
Further, for each element of $A$ $F_1$ we consider $A/\left\{m\right\}$.
This new collection also satisfies the required property,
So $F_1$ has at most $2^{m-2}$ elements.
Thus, if $|F|=2^{m-1}$ then it follows that $|F_1|=|F_2|=2^{m-2}$.
Further, by induction hypothesis,
$F_2$ contains all those subsets of $\{1,2,.....,m-1\}$ with (say) even number of elements.
It then follows that $F_1$ contains all those subsets of $\{1,2,.....,m\}$ which contain the element $m$ and which contains an even number of elements.
This proves that $F$ contains either all the subsets with odd number of elements or all the subsets by even number of elements.