Maths Olympiad Prep

Library / /29 of 54

Combinatorics Difficulty 6.1 National olympiad Prove it China

There are nn new students. Suppose that there are two students who know each other in every three students and there are two students who do not know each other in every four students. Find the maximum value of nn. (posed by Tang Lihua)

Solution

The maximum value of nn is 88.
When n=8n=8, the example shown in the diagram satisfies the requirements, where A1,A2,,A8A_1, A_2, \dots, A_8 represent 88 students. The line segment between AiA_i and AjA_j means AiA_i and AjA_j know each other.
Figure 1

Next, if nn students satisfy the conditions, we want to show that n8n \le 8. To do this, we first prove that the following two cases are impossible.

(1) If someone AA knows at least 66 persons, denoted by B1,B2,,B6B_1, B_2, \dots, B_6. By Ramsey's theorem, there exist 33 persons among them who do not know each other. This contradicts that there are two who know each other in every three students, or that there exist 33 people they know each other. AA and the three persons form a group of four persons such that every two of them know each other. A contradiction.

(2) If some one AA knows at most n5n-5 persons, then in the remaining there are at least 44 persons, none of whom knows AA. Thus every two of the four persons know each other, a contradiction.

When n10n \ge 10, one of (1) and (2) must occur. So such nn does not satisfy the requirements.

If n=9n=9, in order to avoid (1) and (2), each person knows exactly 55 other persons. Thus the number of pairs knowing each other is 9×52N\frac{9 \times 5}{2} \notin \mathbb{N}. This contradiction implies n8n \le 8. Thus the maximum value of nn is 88.

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 and solution reproduced as published; topic and difficulty added by this site.