Problem 1884

For each $k$, denote by $t_k$ the unique integer such that $2^{t_k-1} < k+1 \leq 2^{t_k}$. We show that an $(n, k)$-tournament exists if and only if $2^{t_k}$ divides $n$.

First we prove that if $n = 2^t$ for some $t$ then there is an $(n, k)$-tournament for all $k \leq 2^t - 1$. Let $S$ be the set of $0$-$1$ sequences with length $t$. We label the $2^t$ players with the elements of $S$ in an arbitrary fashion (which is possible as there are exactly $2^t$ sequences in $S$). Players are identified with their labels in the construction below. If $\alpha, \beta \in S$, let $\alpha + \beta \in S$ be the result of the modulo $2$ term-by-term addition of $\alpha$ and $\beta$ (with rules $0+0=0, 0+1=1+0=1, 1+1=0$; there is no carryover). For each $i = 1, \ldots, 2^t - 1$ let $\omega(i) \in S$ be the sequence of base $2$ digits of $i$, completed with leading zeros if necessary to achieve length $t$.

Now define a tournament with $n = 2^t$ players in $k \leq 2^t - 1$ rounds as follows: For all $i = 1, \ldots, k$, let player $\alpha$ meet player $\alpha + \omega(i)$ in round $i$. The tournament is well-defined as $\alpha + \omega(i) \in S$ and $\alpha + \omega(i) = \beta + \omega(i)$ implies $\alpha = \beta$; also $[\alpha + \omega(i)] + \omega(i) = \alpha$ for each $\alpha \in S$ (meaning that player $\alpha + \omega(i)$ meets player $\alpha$ in round $i$, as needed). Each player plays in each round. Next, every two players meet at most once (exactly once if $k = 2^t - 1$), since $\omega(i) \neq \omega(j)$ if $i \neq j$. Thus condition (i) holds true, and condition (ii) is also easy to check.

Let player $\alpha$ meet player $\beta$ in round $i$, player $\gamma$ meet player $\delta$ in round $i$, and player $\alpha$ meet player $\gamma$ in round $j$. Then $\beta = \alpha + \omega(i)$, $\delta = \gamma + \omega(i)$ and $\gamma = \alpha + \omega(j)$. By definition, $\beta$ will play in round $j$ with
$$\beta + \omega(j) = [\alpha + \omega(i)] + \omega(j) = [\alpha + \omega(j)] + \omega(i) = \gamma + \omega(i) = \delta,$$
as required by (ii).

So there exists an $(n, k)$-tournament for pairs $(n, k)$ such that $n = 2^t$ and $k \leq 2^t - 1$. The same conclusion is straightforward for $n$ of the form $n = 2^t s$ and $k \leq 2^t - 1$. Indeed, consider $s$ different $(2^t, k)$-tournaments $T_1, \ldots, T_s$, no two of them having players in common. Their union can be regarded as a $(2^t s, k)$-tournament $T$ where each round is the union of the respective rounds in $T_1, \ldots, T_s$.

In summary, the condition that $2^{t_k}$ divides $n$ is sufficient for an $(n, k)$-tournament to exist. We prove that it is also necessary.

Consider an arbitrary $(n, k)$-tournament. Represent each player by a point and after each round, join by an edge every two players who played in this round. Thus to a round $i = 1, \ldots, k$ there corresponds a graph $G_i$. We say that player $Q$ is an $i$-neighbour of player $P$ if there is a path of edges in $G_i$ from $P$ to $Q$; in other words, if there are players $P = X_1, X_2, \ldots, X_m = Q$ such that player $X_j$ meets player $X_{j+1}$ in one of the first $i$ rounds, $j = 1, 2, \ldots, m-1$. The set of $i$-neighbours of a player will be called its $i$-component. Clearly two $i$-components are either disjoint or coincide.

Hence after each round $i$ the set of players is partitioned into pairwise disjoint $i$-components. So, to achieve our goal, it suffices to show that all $k$-components have size divisible by $2^{t_k}$.

To this end, let us see how the $i$-component $\Gamma$ of a player $A$ changes after round $i+1$. Suppose that $A$ meets player $B$ with $i$-component $\Delta$ in round $i+1$ (components $\Gamma$ and $\Delta$ are not necessarily distinct). We claim that then in round $i+1$ each player from $\Gamma$ meets a player from $\Delta$, and vice versa.

Indeed, let $C$ be any player in $\Gamma$, and let $C$ meet $D$ in round $i+1$. Since $C$ is an $i$-neighbour of $A$, there is a sequence of players $A = X_1, X_2, \ldots, X_m = C$ such that $X_j$ meets $X_{j+1}$ in one of the first $i$ rounds, $j = 1, 2, \ldots, m-1$. Let $X_j$ meet $Y_j$ in round $i+1$, for $j = 1, 2, \ldots, m$; in particular $Y_1 = B$ and $Y_m = D$. Players $Y_j$ exist in view of condition (i). Suppose that $X_j$ and $X_{j+1}$ met in round $r$, where $r \leq i$. Then condition (ii) implies that $Y_j$ and $Y_{j+1}$ met in round $r$, too. Hence $B = Y_1, Y_2, \ldots, Y_m = D$ is a path in $G_i$ from $B$ to $D$. This is to say, $D$ is in the $i$-component $\Delta$ of $B$, as claimed. By symmetry, each player from $\Delta$ meets a player from $\Gamma$ in round $i+1$. It follows in particular that $\Gamma$ and $\Delta$ have the same cardinality.

It is straightforward now that the $(i+1)$-component of $A$ is $\Gamma \cup \Delta$, the union of two sets with the same size. Since $\Gamma$ and $\Delta$ are either disjoint or coincide, we have either $|\Gamma \cup \Delta| = 2|\Gamma|$ or $|\Gamma \cup \Delta| = |\Gamma|$; as usual, $|\cdots|$ denotes the cardinality of a finite set.

Let $\Gamma_1, \ldots, \Gamma_k$ be the consecutive components of a given player $A$. We obtained that either $|\Gamma_{i+1}| = 2|\Gamma_i|$ or $|\Gamma_{i+1}| = |\Gamma_i|$ for $i = 1, \ldots, k-1$. Because $|\Gamma_1| = 2$, each $|\Gamma_i|$ is a power of $2$, $i = 1, \ldots, k-1$. In particular $|\Gamma_k| = 2^u$ for some $u$.

On the other hand, player $A$ has played with $k$ different opponents by (i). All of them belong to $\Gamma_k$, therefore $|\Gamma_k| \geq k+1$.

Thus $2^u \geq k+1$, and since $t_k$ is the least integer satisfying $2^{t_k} \geq k+1$, we conclude that $u \geq t_k$. So the size of each $k$-component is divisible by $2^{t_k}$, which completes the argument.