1

Let $n$ be a natural number and $X$ = {$1,2,...,n$}. For subsets $A$ and $B$ of $X$ we define $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.

bof
  • 78,265
Yellow
  • 375
  • Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$. – ashK Jan 05 '19 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 05 '19 at 10:53
  • 1
    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 05 '19 at 10:55
  • Hey, what happened to the answer? – Yellow Jan 05 '19 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 05 '19 at 17:20

3 Answers3

1

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

J.G.
  • 115,835
0

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.

Mike
  • 20,434
0

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.

Mike
  • 20,434