Maths Olympiad Prep

Library / /91 of 94

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Hong Kong

AA, BB and CC are three persons among a set PP of nn (n3n \ge 3) persons. It is known that AA, BB and CC 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 PP. 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 PP?

Solution

The answer is n12\frac{n-1}{2} if nn is odd, n+22\frac{n+2}{2} if n6n \ge 6 is even, and 44 if n=4n = 4.

Let AA, BB, CC be the sets of friends of AA, BB, CC respectively excluding AA, BB, CC themselves.

Case 1. nn is odd

Since each of AA, BB, CC has at least n+12\frac{n+1}{2} friends, we have A,B,Cn32|A|, |B|, |C| \ge \frac{n-3}{2}. For any person XX other than AA, BB, CC, the set {A,B,X}\{A, B, X\} is a friendly group if and only if X(AB)X \in (A \cap B). Similarly, BC|B \cap C| and CA|C \cap A| count the number of friendly groups of the form {B,C,X}\{B, C, X\} and {C,A,X}\{C, A, X\} respectively. Together with the friendly group {A,B,C}\{A, B, C\}, by the inclusion-exclusion principle, the number of friendly groups is at least

AB+BC+CA+1=A+B+C+ABCABC+1n32×3+0(n3)+1=n12. |A \cap B| + |B \cap C| + |C \cap A| + 1 = |A| + |B| + |C| + |A \cap B \cap C| - |A \cup B \cup C| + 1 \ge \frac{n-3}{2} \times 3 + 0 - (n-3) + 1 = \frac{n-1}{2}.

The minimum value n12\frac{n-1}{2} can be attained. For example, suppose n32\frac{n-3}{2} people are friends of AA and BB, and the other n32\frac{n-3}{2} people are friends of CC. Then {A,B,C}\{A, B, C\} is a friendly group and all other n32\frac{n-3}{2} friendly groups are of the form {A,B,X}\{A, B, X\}.

Case 2. nn is even and n6n \ge 6

Similarly, we have A,B,Cn22|A|, |B|, |C| \ge \frac{n-2}{2}. The number of friendly groups is at least
AB+BC+CA+1=A+B+C+ABCABC+1n22×3+0(n3)+1=n+22. |A \cap B| + |B \cap C| + |C \cap A| + 1 = |A| + |B| + |C| + |A \cap B \cap C| - |A \cup B \cup C| + 1 \ge \frac{n-2}{2} \times 3 + 0 - (n-3) + 1 = \frac{n+2}{2}.

The minimum value n+22\frac{n+2}{2} can be attained. For example, suppose n42\frac{n-4}{2} people are friends of AA and BB, one person is a friend of BB and CC, one person is a friend of CC and AA, and the other n62\frac{n-6}{2} people are friends of CC. Then {A,B,C}\{A, B, C\} is a friendly group. In addition, there are n42\frac{n-4}{2} friendly groups of the form {A,B,X}\{A, B, X\}, one friendly group of the form {B,C,Y}\{B, C, Y\}, and one friendly group of the form {C,A,Z}\{C, A, Z\}.

Case 3. n=4n = 4

Since each of AA, BB, CC has more than 22 friends, every pair of the four people must be friends of each other. Clearly, there are 44 friendly groups.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.