Proving that the given set has at most $2^{n-1}$ elements Let $n$ be a natural number and $X$ = {$1,2,...,n$}. For subsets $A$ and $B$ of $X$ we deﬁne $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∆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.
I have no clue on how and where to start. Please help.
 A: I'll expand on one of bof's comments. If $n>0$ fix some $a\in X$ and pair the subsets of $X$ as $y,\,y\cup\{a\}$ with $a\notin y$. Not both of these are in $F$ because $y\Delta(y\cup\{a\})=\{a\}$, so $|F|$ is at most half the number of subsets of $X$, i.e. $2^{n-1}$ as desired. (I'll leave you to consider the case $n=0$ separately.)
A: Let us write $X=\{1,\ldots, n\}$ and let $P_{n-1}$ be the collection of subsets of $X \setminus \{n\}$. For each $S \in P_{n-1}$, let us define $f(S) = S \cup \{n\}$. Now let $P_n$ be the collection of subsets of $X$. Note that 


*

*$f(S)$ is defined for each $S \in P_{n-1}$;

*$f(S) \not \in P_{n-1}$ for each $S \in P_{n-1}$;

*If $S$ and $S'$ are distinct sets in $P_{n-1}$ then $f(S) \not = f(S')$;

*Therefore $P_{n-1}$ and $\{f(S); S \in P_{n-1}\}$ are disjoint and of equal cardinality, and furthermore, $P_{n-1}$ and $\{f(S); S \in P_{n-1}\}$ partition $P_n$.
So write $P_n = \{S_1,S_2,\ldots, S_{2^n}\}$ where the $S_i$s are distinct and where $f(S_i) = S_{i+1}$ for each odd $i$; this is possible by 1. and 4. together. Then $F$ can contain at most one of $S_i$ and $S_{i+1}$ for each odd $i$, as the disjoint union of $S$ and $f(S)$ is precisely $\{n\}$ which has only 1 < 2 elements.
A: As far as a collection $F$ with $2^{n-1}$ elements, let $F$ be the set of subsets of $X$ of odd cardinality. [Make sure you see why this works]
The set of subsets of $X$ of even cardinality would work too. [Make sure you see why this works] Thus the set of subsets of even cardinality has, by the above answers, only $2^{n-1}$ elements, which implies that the set $F$ of subsets of $X$ of odd cardinality has $2^{n-1}$ elements. And vice versa.
