Maths Olympiad Prep

Library / /26 of 27

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it Croatia

There are 300 contestants at the competition. Each pair of the contestants is either acquainted (knows each other) or unfamiliar with each other, and there are no three contestants who all know each other. Determine the maximum possible nn such that the following conditions hold:
* Every contestant is acquainted with at most nn other contestants.
* For every positive integer mm such that 1mn1 \le m \le n, there is at least one contestant who is acquainted with exactly mm other contestants.
(Mongolia 2017)

Solution

The maximum possible nn is 200200.

Let us assume that there is a contestant, say XX, who knows 201201 other contestants and let those 201201 contestants make up a set SS. There must exist contestants who know exactly 11, 22, \dots, 200200 other contestants.

We will say that the contestant *has degree* mm if he knows exactly mm other contestants.

Each element in SS has degree at most 9999. Namely, he cannot know anyone from SS since there are no three contestants who all know each other (aside from XX and SS, there are only 9898 contestants).

We conclude that contestants from SS have at most 9999 distinct degrees. Simultaneously, there are 9898 contestants not in SS and different from XX, so they can have at most 9898 distinct degrees.

This shows that there are at most 1+99+98=198<2011 + 99 + 98 = 198 < 201 distinct degrees, and therefore it is impossible that there are contestants who know exactly 11, 22, \dots, 201201 other contestants. Hence, there is no contestant who knows exactly 201201 other contestants.

Let us now show that n=200n = 200 is possible. Denote 100100 contestants as A1,A2,,A100A_1, A_2, \dots, A_{100} and call them A-contestants, and the remaining 200200 as B1,B2,,B200B_1, B_2, \dots, B_{200} and call them B-contestants.

For each i{1,2,,100}i \in \{1, 2, \dots, 100\} and each j{1,2,,200}j \in \{1, 2, \dots, 200\}, such that iji \le j, let AiA_i and BjB_j be acquainted. All the other pairs of contestants are unfamiliar with each other. We claim that this example has n=200n = 200, and that all the conditions of the problem are satisfied.

Namely, there are no three contestants who all know each other, because no two A-contestants know each other and no two B-contestants know each other.

Moreso, for i{1,2,,100}i \in \{1, 2, \dots, 100\}, contestant AiA_i knows contestants Bi,Bi+1,,B200B_i, B_{i+1}, \dots, B_{200} and only them. Hence, he has exactly 201i201 - i acquaintances, which means that there are contestants knowing exactly 200200, 199199, \dots, 101101 other contestants. Analogously, for j{1,2,,100}j \in \{1, 2, \dots, 100\}, contestant BjB_j knows A1,,Aj1,AjA_1, \dots, A_{j-1}, A_j and only them. This implies that he has exactly jj acquaintances, which means that there are contestants knowing exactly 11, 22, \dots, 100100 other contestants.

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.