In a group of 5 people, every pair of them could be friends or non-friends. Assume that all possible relationships are equally likely. Find the probability of the event that there are at least three people who are mutually friends. A , B , C are mutual if A is a friend of B and C , B is a friend of A and C and C is a friend of A and b
[Math] Find the probability of the event that there are at least three people who are mutually friends
combinationscombinatoricsgeometrygraph theoryprobability
Related Question
- [Math] Probability of three friends being in the same group — Confusion on Counting
- [Math] Suppose that in a group of 5 people, there are not necessarily three mutual friends or mutual enemies.
- For every set S of at most n people, there is at least one person outside of S who is friends with everyone in S.
- There are $2n$ people on a social media platform. Prove there are at least $5n$ pairs of friends.
Best Answer
Here is an approach that does not rely on Graph Theory:
Suppose we have only 3 people. What is the probability that all three are friends?
That is obviously $2^{-3}$.
Now, suppose there are 4 people. What is the probability that at least three are mutual friends? Well, let's start with the first person A. They can have 0, 1, 2, or 3 friends:
Case 1: A has 0 friends. Now, we are in the same case as above (only 3 people, all must be friends)
Probability: $\dbinom{3}{0}2^{-3}\cdot 2^{-3}$
Case 2: A has 1 friend. It is impossible to set up a set of three friends including A, so again, we are in the same case as above.
Probability: $\dbinom{3}{1}2^{-3}\cdot 2^{-3}$
Case 3: A has 2 friends. In this case, the only way for three of them to be friends is for both of A's friends to be friends. If they are not friends, since they are 2 of the remaining 3 people, it is not possible to find three people that are mutual friends.
Probability: $\dbinom{3}{2}2^{-3}\cdot 2^{-1}$
Case 4: A has 3 friends. Now, the only way for there to not be three mutual friends is if every one of them are not friends.
Probability: $\dbinom{3}{3}2^{-3}\cdot (1-2^{-3})$
Total probability among four people of having at least three mutual friends:
$$\dfrac{23}{2^6}$$
Now, suppose we add another person. That person can have 0, 1, 2, 3, or 4 friends.
Case 1: A has 0 friends, and among the remaining 4, there are at least three mutual friends.
Probability: $\dbinom{4}{0}2^{-4}\cdot \dfrac{23}{2^6}$
Case 2: A has 1 friend, and among the remaining 4, there are at least there mutual friends (note: A cannot be part of any set of three mutual friends).
Probability: $\dbinom{4}{1}2^{-4}\cdot \dfrac{23}{2^6}$
Case 3: A has 2 friends. Now, we can have those friends be friends or those friends not be friends and one of them is part of a group of mutual friends that does not include the other.
Probability: $\dbinom{4}{2}2^{-4}\left( 2^{-1}+2^{-1}(2^{-3}+2^{-3}-2^{-5})\right)$
Case 4: A has 3 friends. Now, if any of those three are also friends, we have a set of three mutual friends, but if none of them are friends, we cannot have a set of three mutual friends.
Probability: $\dbinom{4}{3}2^{-4}(1-2^{-3})$
Case 5: A has 4 friends. Again, if any of these four are also friends, we have a set of three mutual friends, but if none of them are friends, we cannot have a set of three mutual friends.
Probability: $\dbinom{4}{4}2^{-4}(1-2^{-6})$
Total probability that among 5 people, at least three are mutual friends:
$$\dfrac{636}{1024}$$
drhab's answer is much cleaner, of course.