Round Robin Tournament

I thank Professor W. McWorter for bringing this problem to my attention. The problem has been posted to one of the wu:forums.

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.

(The problem makes an implicit assumption that a meet can't end in a draw.)

Solution

Solution

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 G_P a group of players beaten by P. Assume there is a player q not in G_P who, in addition, has not lost to any p in G_P. 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 G_P. Moreover, since he has not lost to either P or any member of the G_P 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 G_P has been beaten by a member of the G_P group.

The problem admits a recasting in terms of Graph Theory. Start with a complete graph K_n, n > 1. (A graph is complete if any two nodes are joined by an edge.) Convert K_n 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.

70549579