, and are three persons among a set of () persons. It is known that , and are friends of one another, and that every one of the three persons has already made friends with more than half the total number of people in . Given that every three persons who are friends of one another form a friendly group, what is the minimum number of friendly groups that may exist in ?
Solution
The answer is if is odd, if is even, and if .
Let , , be the sets of friends of , , respectively excluding , , themselves.
Case 1. is odd
Since each of , , has at least friends, we have . For any person other than , , , the set is a friendly group if and only if . Similarly, and count the number of friendly groups of the form and respectively. Together with the friendly group , by the inclusion-exclusion principle, the number of friendly groups is at least
The minimum value can be attained. For example, suppose people are friends of and , and the other people are friends of . Then is a friendly group and all other friendly groups are of the form .
Case 2. is even and
Similarly, we have . The number of friendly groups is at least
The minimum value can be attained. For example, suppose people are friends of and , one person is a friend of and , one person is a friend of and , and the other people are friends of . Then is a friendly group. In addition, there are friendly groups of the form , one friendly group of the form , and one friendly group of the form .
Case 3.
Since each of , , has more than friends, every pair of the four people must be friends of each other. Clearly, there are friendly groups.