IMO 2006 Shortlisted Problems

For each $k$, denote by $t_k$ the unique integer such that $2^{t_k-1}<k+1\le 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\le 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,\dots ,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\le 2^t-1$ rounds as follows: For all $i=1,\dots ,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)\ne \omega (j)$ if $i\ne 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\le 2^t-1$. The same conclusion is straightforward for $n$ of the form $n=2^{t}s$ and $k\le 2^t-1$. Indeed, consider $s$ different $(2^t,k)$-tournaments $T_1,\dots ,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,\dots ,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,\dots ,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,\dots ,X_m=Q$ such that player $X_j$ meets player $X_{j+1}$ in one of the first $i$ rounds, $j=1,2,\dots ,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,\dots ,X_m=C$ such that $X_j$ meets $X_{j+1}$ in one of the first $i$ rounds, $j=1,2,\dots ,m-1$. Let $X_j$ meet $Y_j$ in round $i+1$, for $j=1,2,\dots ,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\le i$. Then condition (ii) implies that $Y_j$ and $Y_{j+1}$ met in round $r$, too. Hence $B=Y_1,Y_2,\dots ,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,\dots ,{\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,\dots ,k-1$. Because $|{\Gamma }_1|=2$, each $|{\Gamma }_i|$ is a power of $2$, $i=1,\dots ,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|\ge k+1$.

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