$2023$ players participated in a tennis tournament, and any two players played exactly one match. There was no draw in any match, and no player won all the other players. If a player $A$ satisfies the following condition, let $A$ be "skilled player". (Condition) For each player $B$ who won $A$, there is a player $C$ who won $B$ and lost to $A$. It turned out there are exactly $N(\geq 0)$ skilled player. Find the minimum value of $N$.
Problem
Source: KJMO 2023 P4
Tags: combinatorics
04.11.2023 13:46
Answer:$3$. Example for $3$: Let $A,B,C$ be three people such that $A$ won $B$, $B$ won $C$ and $C$ won $A$. Let $v_1,...,v_{2020}$ be the others.$A,B,C$ won all the matches to $v_i'$s and $v_i$ won $v_j$ if $v\geq j$. Let's prove that there are at least $3$ skilled people. Take the person who has the most winnings. There is someone who won $A$. Let this person be $B$. Let $v_1,...,v_k$ be the people who lost to $A$. If at least one of $v_i$ won $B$, then $A,B,v_i$ would be skilled. So $B$ won all $v_i'$s. But then, $B$ won $A,v_1,...,v_k$ Contradiction because $A$ is the person who has the most winnings.
05.11.2023 10:26
We denote $A \rightarrow B$ if $A$ wins $B$. Then we have two lemma, succesively. Lemma 1: In any (directed) graph, (possibly a player won all), the highest outgoing point is skilled. Proof: Let $A$ be the highest outgoing. Suppose that $B \rightarrow A$. By maximality of $A$, there is $C \leftarrow A$ such that $C \rightarrow B$. Lemma 2: For any point $B$, let $H$ be the subgraph consists of the points win $B$. If $H$ is nonempty, then $C$, the highest outgoing point in $H$, is skilled in the whole graph. Proof: $C$ is skilled in $H$ by lemma. Suppose that $B \rightarrow D \rightarrow C$. Then $C \rightarrow B \rightarrow D$ completes the proof. Now let $A$ be the highest outgoing one. Then $A$ is skilled. By the condition the subgraph $H$ which wins $A$ is nonempty and the highest one, say $B$ within $H$ is skilled. By applying lemma 2 again, let $C$ be the highest outgoing within the subgraph which win $B$. Then $C$ is skilled and apparently $C \neq A$. Therefore, at least $3$ points are skilled. $N=3$ can be achieved as the other solution proposed.