TAOCP 5.3.3 Exercise 1
The previous solution fails because it replaces Carroll’s actual tournament mechanism with an invented dominance-based rule and then reasons about that artificial system.
Section 5.3.3: Minimum-Comparison Selection
Exercise 1. [**] [15] In Lewis Carroll’s tournament (Figs. 39 and 40), why was player 13 eliminated in spite of winning in Round 3?
Table 2
MINIMUM AVERAGE COMPARISONS FOR SELECTION
| n | Vi(n) | Va(n) | V3(n) | Va(n) | V5(n) | Ve(n) | V7(n) |
|---|---|---|---|---|---|---|---|
| 1 | 0 | ||||||
| 2 | 1 | 1 | |||||
| 3 | 2 | 2 | 2 | ||||
| 4 | 3 | 4 | 4 | 3 | 4 | 13 | 4 |
| 5 | 4 | 5 | 4 | 5 | 3 | 3 | 5 |
| 6 | 5 | 6 | 5 | 7 | 5 | 7 | 4 |
| 7 | 6 | TH | 8 | 2 | 3 | 9 | 3 |
210 630 105 630 210
Verified: yes
Solve time: 3m39s
The previous solution fails because it replaces Carroll’s actual tournament mechanism with an invented dominance-based rule and then reasons about that artificial system. In the exercise, elimination is not determined by counting inferred losses or by any transitive relation. It is determined entirely by the fixed comparison structure of Carroll’s tournament as shown in Figs. 39 and 40, where the outcome of specific scheduled comparisons decides who advances, independently of later side comparisons.
The key point that the incorrect solution misses is that in Carroll’s scheme a player may participate more than once in the same round in different roles of the comparison structure, and only one of these occurrences is relevant for advancement. Once a player is eliminated by the comparison that feeds into the selection structure, any later comparison involving that player no longer has any effect on the tournament outcome.
To see what happens with player 13, one must follow the actual sequence of comparisons in Round 3 in the figure. Player 13 appears in Round 3 in more than one comparison. In one of these comparisons he is defeated. That loss is the decisive event in the selection structure: it removes him from the set of candidates that can proceed further in the tournament tree. This elimination is immediate in the sense of the tournament construction, because the loser at that node is not propagated further in the winner-selection chain.
After this decisive loss has already occurred, player 13 still appears in a later Round 3 comparison. He wins that later match, but at that point it is no longer a comparison between active candidates for advancement. It is a comparison involving a player who has already been eliminated from the relevant selection path. In Carroll’s construction such a result is recorded but has no effect on who advances, because advancement has already been determined by the earlier comparison in the same round.
Thus the apparent paradox arises from reading Round 3 as a single simultaneous event where all wins and losses have equal status. In the actual tournament structure it is a sequential comparison process embedded in a fixed selection network. Player 13 is eliminated because his first relevant Round 3 comparison is a loss, and that loss determines elimination. His subsequent Round 3 win occurs after his elimination and therefore cannot change his status.