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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

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 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.

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
[an error occurred while processing this directive]