1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$. $\endgroup$ – Ashish K Jan 5 at 10:12
  • $\begingroup$ 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. $\endgroup$ – bof Jan 5 at 10:53
  • 1
    $\begingroup$ 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. $\endgroup$ – bof Jan 5 at 10:55
  • $\begingroup$ Hey, what happened to the answer? $\endgroup$ – Yellow Jan 5 at 12:02
  • $\begingroup$ 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 :/ $\endgroup$ – Yellow Jan 5 at 17:20
0
$\begingroup$

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.

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

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

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

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.

$\endgroup$
  • $\begingroup$ Alright, thank you. $\endgroup$ – Yellow Jan 6 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.