9.9

Q:
In every round robin tennis tournament, there is a player who, for any other player p, has either beaten p or beaten some player who has beaten p.
Zh:
n个人中每两个人之间都进行过一次比赛。假设比赛不可能出现平局。证明，一定能找出这样的一个人，对于其它任何一人p，他击败了p或者击败了某个打败了p的人。

A:
The problem has been characterized as a quickie: once you hit on the right idea, the solution takes just a few lines.

There may be several players with the stated property: for any other player p, this one either beat p or beat a player who has beaten p. The nice idea that makes the problem a quickie is that the player who won most of the games has this property. Let P be such a player and GP a group of players beaten by P. Assume there is a player q not in GP who, in addition, has not lost to any p in GP. Since, it's a round robin tournament, that is a tournament in which every player meets any other player, q met with P and any player from GP. Moreover, since he has not lost to either P or any member of the GP group, he won all those meets implying that he won more meets than P. Contradiction with the selection of P. In other words, any q that is not in GP has been beaten by a member of the GP group.

The problem admits a recasting in terms of Graph Theory. Start with a complete graph Kn, n > 1. (A graph is complete if any two nodes are joined by an edge.) Convert Kn to a directed graph (digraph) by arbitrarily assigning to each edge a direction. The problem stipulates the existence of a node from which any other node is accessible by a directed path of the length at most 2.