2006 IMO Shortlist Problems/C5

Problem

(Argentina) An $(n,k)$ -tournament is a contest with $n$ players held in $k$ rounds such that:

(i) Each player plays in each round, and every two players meet at most once.

(ii) If player $A$ meets player $B$ in round $i$ , player $C$ meets player $D$ on round $i$ , and player $A$ meets player $C$ in round $j$ , then player $B$ meets player $D$ in round $j$ .

Determine all pairs $(n,k)$ for which there exists an $(n,k)$ -tournament.

This problem also appeared on the 2007 TST for Korea.

Solution

Let $t$ be the greatest integer such that $2^t$ divides $n$ . Then there exists an $(n,k)$ -tournament if and only if $k \le 2^t - 1$ .

We first prove that if $k \le 2^t - 1$ , then there exists an $(n,k)$ -tournament. Since we may partition our $n$ players into $n/2^t$ different groups of size $2^t$ , it suffices to prove this for $n=2^t$ .

To this end, let us label the $2^t$ players with the elements of $(\mathbb{Z}/2\mathbb{Z})^t$ , and label the different rounds with distinct nonzero elements of $(\mathbb{Z}/2\mathbb{Z})^t$ . In the round with label $j$ , let player $a$ meet player $a+j$ . We then have a $(2^t,k)$ tournament, for if $a-b = c-d = i$ , then $a-c = b-d$ , for all $a,b,c,d \in (\mathbb{Z}/2\mathbb{Z})^t$ .

We next prove that if $k > 2^t-1$ , then there is no $(n,k)$ -tournament. For this, we first prove an intermediate result.

Lemma. The number of players in any minimal subtournament of an $(n,k)$ -tournament is a power of 2.

Proof. We induct on $k$ . The case $k=0$ is trivial.

Suppose now that all minimal subtournaments of any $(n,k-1)$ -tournament have sizes that are powers of 2. Then in any $(n,k)$ -tournament, the minimal subtournaments, ignoring the last round, are of powers of 2. Let $S$ be the set of players for such a minimal tournament, and for any player $a$ in the $(n,k)$ -tournament, let $K(a)$ be the player $a$ meets in round $k$ . Then either $K(S) = S$ , or $K(S)$ and $S$ are disjoint; furthermore, $K$ induces an isomorphism of tournaments from $S$ to $K(S)$ , so $S$ and $K(S)$ have the same cardinality. It follows that the minimal subtournament of the $(n,k)$ -tournament containing any element of $S$ has size either $|S|$ or $2|S|$ , completing the inductve step and proving the lemma. $\blacksquare$

Now, suppose that there exists an $(n,k)$ -tournament for $k > 2^t-1$ . Then every minimal sub-tournament of our tournament has a multiple of $2^{t+1}$ players, since each must have a size that is a power of 2, and no two players meet more than once. It follows that $2^{t+1}$ divides $n$ , a contradiction. Therefore no $(n,k)$ -tournament exists for $k > 2^t-1$ , as desired. $\blacksquare$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

2006 IMO Shortlist Problems
<url>viewtopic.php?p=875001#875001 Discussion on AoPS/MathLinks</url>

Page

Toolbox

Search

2006 IMO Shortlist Problems/C5

Problem

Solution

Resources