Problem 1111

Solution. We will prove the statement using the principle of mathematical induction. For $k=2$, the group consists of $2n$ people. Any person in the group knows more than $(2-1)n=n>1$ members of the group, so there are at least two people who know each other. Each of them knows more than $n$ members of the group. Let the set of people known to one of them be denoted by $A$ and the set of people known to the other be denoted by $B$. Therefore, $|A|>n$ and $|B|>n$. Using the formula $|A \cup B|=|A|+|B|-|A \cap B|$, we get

$$|A \cup B|=|A|+|B|-|A \cap B|>n+n-|A \cap B|=2n-|A \cap B|$$

If $|A \cap B|=0$, then $|A \cup B|>2n$, which is impossible. Therefore, $|A \cap B|>0$, i.e., $A \cap B \neq \varnothing$. This means there is at least one member of the group who belongs to both sets $A$ and $B$. Thus, this person knows both of the selected members of the group. Since the two members of the group were chosen to know each other, we conclude that the trio knows each other. Therefore, the statement is true for $k=2$.

Assume the statement is true for $k=m$, i.e., in a group of $mn$ people where each person knows more than $(m-1)n$ others, there are at least $m+1$ of them who know each other pairwise.

For $k=m+1$, let us have a group of $(m+1)n$ people, where each of them knows more than $mn$ people in the group. We will choose one member of the group, who, according to the assumption, knows more than $mn$ members of the group. Therefore, we can select exactly $mn$ members of the group whom he knows. From the new group of $mn$ members, each of them knows more than $(m-1)n$ of them (from the original group, at most $n-1$ members with whom he is acquainted are removed, so he knows at least $mn-(n-1)$ members of the selected group. Or from the group of $mn$ members who are selected, each of them knows more than $mn$ members of the original group of $(m+1)n$ people. Since $n$ members are removed from the original group, he knows more than $mn-n$ members of the selected group). Therefore, in the selected group of $mn$ members, each of them knows more than $(m-1)n$ of them. According to the inductive hypothesis, there are $m+1$ people in the selected group of $mn$ members who know each other pairwise. Together with the person initially selected, they form a group of $m+2$ people in which any two know each other.

According to the principle of mathematical induction, the statement is true, i.e., in a group of $kn$ people where each knows more than $(k-1)n$ of the others, there are $k+1$ members of the group such that any two of them know each other.