2006 IMO Shortlist Problems/C5

Revision as of 10:09, 30 March 2008 by Boy Soprano II (talk | contribs) (problem and solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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