# There is one set with 6 member(A). if we subsets $A_1 ,A_2, …,A_k$ choosed from $A$ so that $(i \ne j)$ and has hold $A_i \ne A_j \cup\{x\}$.

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$?

-
I edited your post for clarity. Please check that I did not alter your intended meaning. – David Mitra Dec 13 '12 at 15:41
@DavidMitra Thanks for edit. – World Dec 13 '12 at 15:44
Do you mean: For all $i\neq j$ and all $x\in A$, $A_i\neq A_j\cup \{x\}$? – Thomas Andrews Dec 13 '12 at 16:28

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

-
1)I don't know how to group subsets of A into pairs? 2) $\{B, B \cup \{a\}\}$ is $\{A_i, A_j \cup \{a\}\}$ 3)final ansewr is 32? – World Dec 13 '12 at 16:11
I mean group all subsets of $A$ into pairs that just differ by whether $a$ belongs to them or not. If $A=\{a,b,c,d,e,f\}$, some examples of the pairs of subsets I'm talking about are $\{\{b,d\},\{a,b,d\}\}$, $\{\emptyset,\{a\}\}$, $\{\{f\},\{a,f\}\}$, etc. Out of each such pair at most one of the two subsets can be chosen as an $A_j$. – Omar Antolín-Camarena Dec 13 '12 at 16:28
Can we say maximum k is 32 because A={b,c,d,e,f} without a ?? – World Dec 13 '12 at 16:48
@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. – Omar Antolín-Camarena Dec 13 '12 at 17:27