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

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

- Graphs Fundamentals
- Crossing Number of a Graph
- Regular Polyhedra
- 3 Utilities Puzzle: Water, Gas, Electricity
- A Clique of Acquaintances
- Round Robin Tournament
- The Affirmative Action Problem
- The Two Men of Tibet Problem
- Euler Cycles in Digraph
- Fleury's Algorithm and Euler's Paths and Cycles: an Interactive Gizmo
- Graph with Nodes of Even Degree
- Graph without 3-Cycles

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

Copyright © 1996-2018 Alexander Bogomolny

65271936 |