Tell me more ×
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.
up vote 0 down vote favorite

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 ?

share|improve this question
1  
Are any two people either friends or strangers, but not both? And is the stranger relation commutative? – Harald Hanche-Olsen Sep 17 '12 at 15:06
Question edited to clarify this point. – true blue anil Sep 17 '12 at 15:13

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
Thanks a lot, I was mistaken in thinking that it related to the friends and strangers theorem. – true blue anil Sep 18 '12 at 3:16
@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. – Einar Rødland Sep 18 '12 at 4:26

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.