After Round Robin, there is always a player such that every other was either beaten by him or beaten by a player beaten by him Every participant of a tournament plays with every other participant exactly once. No game is a draw. After the tournament, every player makes a list with the names of all the players, who either were beaten by him or were beaten by a player beaten by him. Prove that there is a player whose list contains the names of all other players.
 A: Let's use induction on the number of participants.
If there is exactly one participant, the situation is pretty clear. So suppose that there are $n \geq 2$ participants, and that we have solved the problem for $n-1$ participants.
Let us consider a participant $v$, and take a look at the remaining participants. Among them, we can select a "winner" $w$ such that for each participant (apart from $v$) either he was beaten by $w$, or he was beaten by someone who was beaten by $w$. Let $A$ denote the set of those who were defeated by $w$, and let $B$ denote the rest, so that we know that everyone in $B$ was beaten by someone in $A$. 
Now, consider the results of games that $v$ played. If he lost to $w$, then we are done - the choice of $w$ still "works". Similarly, if $v$ lost to someone in $A$, then we are done - $w$ still works. Thus, we can assume that $v$ won with $w$ and with everyone in $A$.
But now $v$ has everyone on his list: 


*

*$w$ is there, because $v$ won against $w$;

*everyone in $A$ is there for the same reason; 

*everyone in $B$ is there, because everyone in $B$ lost to someone in $A$, and $v$ won with everyone in $A$.


Thus, in this case $v$ can be chosen, because for each player $v$ either won against him (for $w$ and $B$), or $v$ won against someone who won against him (for $B$). Hence, and we are done. 
A: We will prove this problem by using induction. 


*

*For $n=2$ it is pretty obvious that this is true - no matter what the outcome of the only match is there always would be a player which has the other player in his list.

*Suppose that the statement is true for $n-1$. So there would be a player $P_i$ which satisfies the condition, i.e. if $B_{d}(P_i)$ is the set of all player beaten directly by player $P_i$ and $B_{nd}(P_i)$ is the set of all players beaten by a player beaten by $P_0$ (but not directly beaten by $P_i$) then $B_n(P_i) \cap B_{nd}(P_i) = \emptyset$ and $B_n(P_i) \cup B_{nd}(P_i) =$$ \{P_1, P_2, \dots, P_{n-1}\}\setminus {P_i}$. Lets consider another player and suppose that this new $P_n$ is not on the list of $P_i$ (otherwise $P_i$ would be the person we are looking for). This means that $P_n \not \in B_n(P_i) \rightarrow P_i \in B_n(P_n)$ and $P_n \not \in B_{nd}(P_i) \rightarrow (\forall P_j \in B_n(P_i))(P_j \in B_n(P_n)) \rightarrow $$(\forall P_j \in B_{nd}(P_i))(P_j \in B_{nd}(P_n))$. So we see that $P_n$ would have every other player in his list. $\blacksquare$ 

