Among a group of 120 people, some pairs are friends. A weak quartet is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets ?
Solution
Given a group of 120 people, where some pairs are friends, we need to determine the maximum possible number of weak quartets. A weak quartet is defined as a set of four people containing exactly one pair of friends.
To solve this, we need to analyze the structure of weak quartets:
1. Count the total number of quartets:
The total number of ways to choose 4 people out of 120 is given by the combination formula:
2. Count the number of quartets that could be considered as weak quartets:
First, select a pair of friends, and then choose the other two people from the 118 remaining people. If is the number of pairs of friends, then:
3. Maximize the number of weak quartets:
To maximize the number of weak quartets, assume the maximum possible number of friendship pairs. According to the combinatorial principle, the maximum number of friendship pairs among 120 people occurs when every possible pair of persons is friends:
4. Thus, the maximum possible number of weak quartets is:
Therefore, the maximum possible number of weak quartets is: