## Task A-4.5.

In a competition, 300 contestants participate. Any two contestants either know each other or do not know each other, and there do not exist three contestants who all know each other. Determine the largest possible value of the number $n$ such that the following conditions are satisfied:

- Each contestant knows at most $n$ other contestants.
- For every natural number $m$ such that $1 \leqslant m \leqslant n$, there exists at least one contestant who knows exactly $m$ other contestants.
## Solution.

The largest possible value of the number $n$ is 200.

Assume there is a contestant, let's call him $X$, who knows 201 other contestants, and let these 201 contestants form the set $S$. Therefore, there must be contestants who know exactly $1, 2, \ldots, 200$ other contestants.

We say that a contestant has degree $m$ if they know exactly $m$ other contestants.

Each contestant in the set $S$ has a degree of at most 99. Indeed, they cannot know anyone in $S$ because there are no three contestants who all know each other, and apart from $X$ and the contestants in $S$, there are only 98 other contestants. Therefore, the contestants in $S$ have at most 99 different degrees. At the same time, there are 98 contestants who are not in $S$ and are not $X$, so they have at most 98 different degrees.

Thus, we have shown that the contestants have at most $1 + 99 + 98 = 198 < 201$ different degrees, so it is impossible for there to be contestants who know exactly $1, 2, \ldots, 201$ other contestants. Therefore, there is no contestant who knows exactly 201 other contestants.

Now, let's show that it is possible for $n = 200$. Let 100 contestants be denoted by $A_{1}, A_{2}, \ldots, A_{100}$ and call them $A$-contestants, and the remaining 200 by $B_{1}, B_{2}, \ldots, B_{200}$ and call them $B$-contestants.

For each $i \in \{1, 2, \ldots, 100\}$ and each $j \in \{1, 2, \ldots, 200\}$, such that $i \leqslant j$, let contestants $A_{i}$ and $B_{j}$ know each other. All other pairs of contestants do not know each other. We claim that for this arrangement of acquaintances, $n = 200$ and all conditions of the problem are satisfied.

Indeed, 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.

Furthermore, for $i \in \{1, 2, \ldots, 100\}$, contestant $A_{i}$ knows contestants $B_{i}, B_{i+1}, \ldots, B_{200}$ and only them. Thus, they have exactly $201 - i$ acquaintances, which means there are contestants who know exactly $200, 199, \ldots, 101$ other contestants. Similarly, for $j \in \{1, 2, \ldots, 100\}$, contestant $B_{j}$ knows contestants $A_{1}, \ldots, A_{j-1}, A_{j}$ and only them. That is, they have exactly $j$ acquaintances, which means there are contestants who know exactly $1, 2, \ldots, 100$ other contestants.