0
$\begingroup$

How to solve this problem?

There is a set $A$ with 6 members. Suppose we choose $k$ subsets $A_1 ,A_2, ...,A_k$ of $A$ so that $A_i \ne A_j \cup\{x\}$ whenever $i\ne j$.

What is maximum value of such a $k$?

  • 0
    Do you mean: For all $i\neq j$ and all $x\in A$, $A_i\neq A_j\cup \{x\}$?2012-12-13

1 Answers 1

2

By taking all sets of even cardinality we can achieve $2^5=32$ sets with the desired property. We can't do better for the following reason: pick a fixed element $a$ of $A$ and group all subsets of $A$ into pairs $\{B, B \cup \{a\}\}$ (where $B$ ranges over all subsets of $A$ that do not contain $a$); for the $A_j$'s you can pick at most one from each pair, and so at most half the subsets.

This argument shows that for a set $A$ with $n$ members the answer is $2^{n-1}$. Here's how it works in detail for $A$ with three elements, say $A = \{1,2,3\}$ (I'll take $a=1$ in the above argument). $A$ has eight subsets in this example which you can arrange in 4 pairs as follows:

  1. $\emptyset$ and $\{1\}$
  2. $\{2\}$ and $\{1,2\}$
  3. $\{3\}$ and $\{1,3\}$
  4. $\{2,3\}$ and $\{1,2,3\}$

If you want to choose subsets $A_j$ of $A$ satisfying the condition in the problem, you can't choose two subsets from the same pair, since those two would satisfy $A_i = A_j \cup \{1\}$. This shows we cannot have $k>4$. But we can get $k=4$, by picking from each pair the set that has an even number of members: $\emptyset, \{1,2\}, \{1,3\}, \{2,3\}$. (Picking sets with an odd number of elements also works.)

  • 0
    @World, the maximum is 32, but not for the reason you wrote (which frankly, I can't make sense of). I'll try to add$a$clear example to the answer.2012-12-13