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>