Puzzle:
An N-player "tournament" in this puzzle shall mean an antisymmetric N×N matrix whose
off-diagonal entries are each ±1.
The entry in position AB is + if player A beat player B in the round-robin tournament.
A "beatpath" from A to Z is an ordered sequence of players ABC...Z
such that A beat B, and B beat C, and ... beat Z.
If an X→Y beatpath exists for every ordered player-pair (X,Y), then
the tournament is called "strongly connected" or just "strong" for short.
A "king" in a tournament is a player K such that for all rivals X, either K beats X directly,
or there exists some Y such that KYX is a 2-hop beatpath.
The "directed distance" from X to Y is the number of hops in the shortest beatpath from X to Y.
(Note: this in general differs from the distance from Y to X.)
The "diameter" of a tournament is the maximum distance from X to Y over all ordered pairs (X,Y).
If the tournament is not strong, the diameter is infinity.
a. Prove every tournament contains at least one king. (Hint: show any player who beats the maximum number of rivals, is a king.)
b. Prove every strong tournament has 2≤diameter≤N-1, and the upper bound is attained by a unique tournament.
c. Prove that the average distance from X to Y, over all ordered pairs (X,Y) of players in an N-player strong tournament, obeys 3/2≤D≤(N+4)/6 with both bounds being tight for an infinite subset of the N≥3.
a. Apparently the "king exists" theorem was first stated by
H.G. Landau: On dominance relations and the structure of animal societies, III, Bulletin of Mathematical Biophysics 15,2 (1953) 143-148.
A very simple proof using our hint is as follows: Whoever wins the most matches is a king. (There might be several tied; in that case they all are kings.) Because: such a player K either beats A directly, or: the set of players K beats must differ from the set A beats and hence there must exist a player X whom K beats but A does not. Then KXA is a 2-hop beatpath. Q.E.D.
b. Diameter=1 is not possible if N≥2 since if A beats B, then B does not beat A. Diameter=2 is possible – and is achieved exactly in "all-kings" strong tournaments. By puzzle 26c almost every N-player tournament has diameter=2 in the limit when N is large. That indeed proves all-kings tournaments exist for all sufficiently large N, which reduces the problem to a finite number of cases... and then for each smaller N we can construct examples manually... Except there is a slight asterisk to this: diameter=2 is not possible when N=4 – since an all-kings 4-player tournament is not possible as one can verify by constructing all possibilities – and then diameter=3 is the only finite allowed value (also, when N=2 of course finite diameter is impossible). But all-kings N-player tournaments do exist for each N≥3 except N=4.
Obviously if diameter≥N the (≥N)-hop beatpath from X to Y would need to revisit some vertex in which case the "loop" could be surgically removed showing it was not the shortest X→Y beatpath. Avoiding that contradiction forces diameter≤N-1. To see this can be tight, Rob LeGrand gives the following rank-order ballot election
| #voters | Their vote |
| 29 | A > C > B > D |
| 15 | B > D > A > C |
| 16 | D > C > B > A |
with 4×4 defeat-margins matrix
* A B C D A * -2 +28 -2 B +2 * -30 +28 C -28 +30 * -2 D +2 -28 +2 *
whose signs (i.e. pairwise defeat relationships) instantiate a 4-player tournament with king D, but A requires 3 hops to defeat D, since the only 2-long beatpath from A is ACB. Therefore A is a non-king and diameter=3.
More generally, the N×N sign pattern
* + - - - - - * + - - - + - * + - - + + - * + - + + + - * + + + + + - *
featuring +s along the diagonal just above the central diagonal, with all other entries in upper triangle -, obviously yields diameter=N-1 with longest min-distance beatpath ABC...Z. This beatpath wlog can be taken (by renaming the players if necessary) to be the just-above-central diagonal, and then all other entries in the upper triangle are forced to be "-" to avoid shortening the A→Z beatpath, thus showing this tournament is the unique one with diameter=N-1, for each N≥3.
I further claim it always is possible to instantiate this tournament via an N-candidate rank-order ballot election (proven in part e of this puzzle). Indeed we can by that same argument show one exists, for each N≥4, in which (like LeGrand's example) the (N-1)-hop beatpath happens to be the unique "strongest" beatpath (i.e. with minimum margin maximized).
c. This result is proved (among many others) by
Jan Plesnik: On the sum of all distances in a graph or digraph, J. Graph Theory 8,1 (1984) 1-24.
Plesnik also shows: The lower bound 3/2 is tight for every all-kings tournament. The upper bound is tight exactly for the unique max-diameter strong tournament.
Postscript. I have not seen it, but
M. Harminc & Jaroslav Ivanco: Note on eccentricities in tournaments, Graphs and Combinatorics 10,2 (1994) 231-234
probably also is relevant to all this.