# 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.

• Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$. – Ashish K Jan 5 at 10:12
• It's not necessary, but I find it more pleasant to think of such a problem in terms of binary words (bitstrings) of length $n$ instead of subsets. You want a set of binary codewords of length $n$ such that any two different codewords differ in at least $2$ places, a so-called single error detecting code. – bof Jan 5 at 10:53
• To see that you can't have more than $2^{n-1}$, observe that the $2^n$ subsets (or words) can be partitioned into pairs, so that each pair differs only in one place; thus your collection can't include more than one from each pair, so it can't contain more than half of the $2^n$ sets. – bof Jan 5 at 10:55
• Hey, what happened to the answer? – Yellow Jan 5 at 12:02
• Can anyone post a full solution to this problem? I have been trying it for long, but I dont think I got any useful or nice solution :/ – Yellow Jan 5 at 17:20

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

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

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

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

4. 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.

• Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how? – Yellow Jan 6 at 16:18
• See below...... – Mike Jan 6 at 16:59

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.)

• This solution is fine, too. But the second part? – Yellow Jan 6 at 16:24

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.

• Alright, thank you. – Yellow Jan 6 at 18:25