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.

There's a set $S$ with $8$ elements. How many distinct $3-$element subsets of $S$ are possible such that the intersection of any $2$ of them is not a $2-$element set?

Please help. I think its $14$. The options are :

  1. $28$
  2. $56$
  3. $112$
  4. $14$
  5. $168$
share|improve this question
1  
The question is unclear. Do you want to know the maximum size of such collections of 3-elements subsets, or do you want to know how many such collections are possible? In either case I don't think the answer appears among the given choices. Also, what makes you favor 14? –  Generic Human Jul 23 '12 at 12:21
    
Is your reason for thinking it's 14 that you have actually found 14 such 3-element subsets? Can you show us? –  Gerry Myerson Jul 23 '12 at 12:46

2 Answers 2

Well, there are $\,\binom{8}{3}=56\,$ different subsets with 3 elements in a set with 8 elements, so this already rules out 3 of your 5 options (can you see which ones?).

Now begin doing some maths, for example: let the set be $\,\{1,2,3,4,5,6,7,8\}\,$ , and choose one of these 3-sets, say $\,\{1,2,3\}\,$. How many 3-sets are there with at most one element in common with this set? Well, exactly $\,\binom{6}{3}=20\,$ (can you see why?). Now add to these the set $\,\{1,2,3\}\,$ itself...

Try now to polish and finish the argument.

share|improve this answer

Each number is contained in at most three sets. Indeed, all sets which contain, say, $1$ are not alowed to share any more elements. Since there are just $7$ other elements, there are at most $\lfloor \frac{7}{2}\rfloor=3$ possibilities. Thus if we list all sets which contain $1$ then all sets which contain $2$ etc. we end up with at most $24$ sets. But we have counted each of them three times, so the maximum is at most $8$. This number is attended with $(123)(456)(147)(257)(367)(158)(268)(348)$.

share|improve this answer

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.