I found this problem in my Norwegian calculus book. I think it's difficult.
A pool/billiards tournament has n participants. Everyone plays one game against each of the other players.
a) Show that no matter how the games end, it will be possible after the
tournament to make a list of all players such that each player has beaten
the next player in the list in the match they played against each other. (Note: A pool game cannot end as a draw.)
b) (This can be proved by induction, but it might be easier to prove it by other means). We say that a group of players stands out if all the players in the group has beaten all the players who are not part of the group. Assume there is no such group that stands out in this way. Show that no matter which players A, B we pick, there is a list A, X, Y, Z … B where every player on the list has beaten the next one in the match they played against each other. (The list doesn't have to contain every player in the tournament).
Best Answer
I have no idea what these problems were doing in a calculus text. They would be relatively elementary problems in a graph theory text.
Benjamin Arvola did a good job of tackling the first problem in his solution, so I'll handle the second.
Let $A$ be a player in the tournament, and let $S$ be the set of all players that $A$ dominates (in the sense that there is a chain of players starting with $A$ such that each player in the chain beat the next player). We want to be convinced that $S$ is the set of all players. Assume that it isn't, so that $S'$ - the set of all players that were not dominated by $A$ - is non-empty. This means that every member of $S'$ beat every member in $S$, because otherwise $S$ could have been extended. But that is precisely $S'$ standing out, which we were told didn't happen in this tournament. Therefore, by contradiction, $S'$ is empty and $A$ must have dominated everyone in the tournament (as did everyone else, since $A$ was arbitrarily chosen).