1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

I have an answer for a), but not b

We use strong induction on n. Let P(n) be the predicate that in every n-player round-robin (pool) tournament where games cannot end with a draw, there exists a ranking $p_1, p_2, . . . , p_n$ of the players such that pi defeats pi+1 for all i = 1, . . . , n−1. In the base case n = 0, there are no players, so there is nothing to prove. Therefore P(0) trivially holds. (One may also define n = 1 to be the base case, in which case the result also holds trivially. In fact it even holds trivially for n = 2.)

In the inductive step, assume that such a ranking exists for every tournament with up to k ≥ 0 players in order to prove that such a ranking exists in a tournament with k + 1 players. Choose an arbitrary player x. Let B(x) be the set of players that beat x and let L(x) be the set of players that lose to x. Note that any of these sets have at most k players and that either might be empty.

Let b = |B(x)|. Then 0 ≤ b ≤ k and by the induction hypothesis, there exists a ranking of the players in B(x), say $p_1, . . . , p_b$ such that pi defeats pi+1 for all $i \in {1, . . . , b − 1}$. Similarly, as $0 ≤ |A(x)| = (k + 1) − 1 − b = k − b ≤ k$, there exists a ranking of the players in B(x), say $p_{b+2}, . . . , p_{k+1}$ such that $p_i$ defeats $p_{i+1}$, for all $i \in {b + 2, . . . , k}$.

Set $p_{b+1} = x$. Then $p_1, . . . , p_b, p_{b+1}, p_{b+2}, . . . , p_{k+1}$ is a ranking of all the players. By construction, $p_i$ defeats $p_{i+1}$. whenever $i \neq b, b + 1$. In addition, we know that $p_b$ defeats $x = p_{b+1}$ since $p_b \in B(x)$ and that $x = p_{b+1}$ defeats $p_{b+2}$ since $p_{b+2} \in L(x)$. Thus, $p_1, . . . , p_b, p_{b+1}, p_{b+2}, . . . , p_{k+1}$ is the desired ranking.

$\endgroup$
1
  • $\begingroup$ You can get by with regular (as opposed to strong) induction: In going from $k$ to $k+1$, simply place the new player above the first player in the already established list whom he or she beats (and put them at the bottom of the list if they don't beat anyone). $\endgroup$ Commented Nov 18, 2019 at 10:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .