[ Combinations and Permutations ]
[ $\underline{\text { Directed Graphs }}$ ]

In the discussion, 15 deputies participated. Each of them, in their speech, criticized exactly $k$ of the remaining 14 deputies.

For what smallest $k$ can we assert that there will be two deputies who criticized each other?
Consider a directed graph where the vertices correspond to deputies, and an edge leading from $A$ to $B$ means that deputy $A$ has criticized deputy $B$.

## Solution

If each deputy has criticized 8 others, then the number of edges in the graph is $15 \cdot 8 = 120$, which is greater than the number of pairs $C_{15}^{2} = 105$ of its vertices. This proves that some two vertices are connected by at least two edges, meaning that there will be two deputies who have criticized each other.

On the other hand, suppose 15 deputies are sitting around a round table and each has criticized the seven deputies sitting next to them in a clockwise direction. It is easy to see that in this case, no two deputies have criticized each other.

## Answer

For $k=8$.