Maths Olympiad Prep

Library / /111 of 155

Combinatorics Difficulty 6.6 National olympiad Prove it Saudi Arabia

Let 300 students participate to the Olympiad. Between each 3 participants there is a pair that are not friends. Hamza enumerates participants in some order and denotes by xix_{i} the number of friends of ii-th participant. It occurs that
{x1,x2,,x299,x300}={1,2,,N1,N}. \left\{x_{1}, x_{2}, \ldots, x_{299}, x_{300}\right\}=\{1,2, \ldots, N-1, N\} .
Find the biggest possible value for NN.

Solution

Firstly, we shall prove that if A,BA, B are friend then the sum of friends of each one does not exceed 300300. Indeed,
Suppose that AA has aNa \leq N friends and BB has bNb \leq N friends. Note that AA and BB cannot have any common friend; otherwise, take CC as a friend of A,BA, B and then the triple (A,B,CA, B, C) does not satisfy the given condition. Thus
(a1)+(b1)298 and a+b300. (a-1)+(b-1) \leq 298 \text{ and } a+b \leq 300.
Suppose that N201N \geq 201 and take some student XX who has 201201 friends. Take YY who has at least 100100 friends, then as the remark above, XX and YY are not friends. Note that we always can find 100100 distinct students and each of them has exactly 100,101,,200100,101, \ldots, 200 friends, and they are not friends of XX. So the number of friends of XX is less than 200200, contradiction. Therefore, N200N \leq 200.

We can give an example as follows. Divide students into groups A={A1,A2,,A200}A=\left\{A_{1}, A_{2}, \ldots, A_{200}\right\} and B={B1,B2,,B100}B=\left\{B_{1}, B_{2}, \ldots, B_{100}\right\}.

- Student B1B_{1} is friends with all students in AA.
- Student B2B_{2} is friends with all students from A2A_{2} to A200A_{200}.
- ...
- Student B100B_{100} is friends with students from A100A_{100} to A200A_{200}.
- Students in the same group are not friends.

So it is easy to check that there are no any triplet of students that are friends with each other. And the number of friends of students in AA is 1,2,,1001,2, \ldots, 100 and the number of friends of students in BB is 200,199,,101200,199, \ldots, 101.

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.