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 :
- $28$
- $56$
- $112$
- $14$
- $168$
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 :
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.
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)$.