0
$\begingroup$

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$
  • 0
    Is your reason for thinking it's 14 that you have actually found 14 such 3-element subsets? Can you show us?2012-07-23

2 Answers 2

1

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.

1

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