Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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