1
$\begingroup$

There is a group of $20$ people. Each pair of people are either friends or strangers, and each person finds exactly $6$ strangers in the group. If all possible committees of $3$ are formed from the group, what is the total $\#$ of committees consisting of all friends or all strangers ?

  • 0
    Question edited to clarify this point.2012-09-17

1 Answers 1

3

In each 3-group where the three memeber are not all friends or all strangers, there will be two members for which the two other members are one friend and one stranger.

So let's count the number of ways to pick such a 3-group and member.

If there are $N$ 3-groups containing both friends and strangers, the 3-group and member having both friend and stranger can be picked in $2N$ different ways.

On the other hand, if we pick any one of the 20 persons, we can pick one friend and one stranger in $6\times13$ different ways, and the 3-group and member pairs can all be produced in this manner. Hence, $2N=20\times6\times13$ which makes $N=780$.

The total number of ways to pick 3-groups of any kind is ${20\choose3}=1140$. Hence, the number of ways to pick a 3-group with either all friends or all strangers is $1170-780=360$.

  • 0
    @trueblueanil Actually, one of the reasons I solved it so quickly was that the problem text contained an extremely strong hint. It stated clearly that the number of 3-groups with all friends or all strangers would be completely determined, which was not at all clear a priori. Initially, I saw no particular reason why this had to be the case. However, once the text had made that clear, a simple counting strategy, i.e. find some object (3-group and particular member as specified in the answer) and count it in two different ways, was an obvious strategy.2012-09-18