2006 IMO Shortlist Problems/C5
Problem
(Argentina) An -tournament is a contest with
players held in
rounds such that:
- (i) Each player plays in each round, and every two players meet at most once.
- (ii) If player
meets player
in round
, player
meets player
on round
, and player
meets player
in round
, then player
meets player
in round
.
Determine all pairs for which there exists an
-tournament.
This problem also appeared on the 2007 TST for Korea.
Solution
Let be the greatest integer such that
divides
. Then there exists an
-tournament if and only if
.
We first prove that if , then there exists an
-tournament. Since we may partition our
players into
different groups of size
, it suffices to prove this for
.
To this end, let us label the players with the elements of
, and label the different rounds with distinct nonzero elements of
. In the round with label
, let player
meet player
. We then have a
tournament, for if
, then
, for all
.
We next prove that if , then there is no
-tournament. For this, we first prove an intermediate result.
Lemma. The number of players in any minimal subtournament of an -tournament is a power of 2.
Proof. We induct on . The case
is trivial.
Suppose now that all minimal subtournaments of any -tournament have sizes that are powers of 2. Then in any
-tournament, the minimal subtournaments, ignoring the last round, are of powers of 2. Let
be the set of players for such a minimal tournament, and for any player
in the
-tournament, let
be the player
meets in round
. Then either
, or
and
are disjoint; furthermore,
induces an isomorphism of tournaments from
to
, so
and
have the same cardinality. It follows that the minimal subtournament of the
-tournament containing any element of
has size either
or
, completing the inductve step and proving the lemma.
Now, suppose that there exists an -tournament for
. Then every minimal sub-tournament of our tournament has a multiple of
players, since each must have a size that is a power of 2, and no two players meet more than once. It follows that
divides
, a contradiction. Therefore no
-tournament exists for
, as desired.
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>