In a round robin chess tournament each player plays every other player exactly once. The winner of each game gets $ 1$ point and the loser gets $ 0$ points. If the game is tied, each player gets $ 0.5$ points. Given a positive integer $ m$, a tournament is said to have property $ P(m)$ if the following holds: among every set $ S$ of $ m$ players, there is one player who won all her games against the other $ m-1$ players in $ S$ and one player who lost all her games against the other $ m - 1$ players in $ S$. For a given integer $ m \ge 4$, determine the minimum value of $ n$ (as a function of $ m$) such that the following holds: in every $ n$-player round robin chess tournament with property $ P(m)$, the final scores of the $ n$ players are all distinct.
Problem
Source: CGMO 2007 P8
Tags: function, combinatorics unsolved, combinatorics
04.02.2011 11:52
Answer: $2m-4$ Consider an arbitrary tournament with property $P(m)$ with $n\ge2m-3$ players. We call a set $S$ of $m$ players "good" if there is a player who won all her games against the other $m-1$ players in $S$ and a player who lost all her games against the other $m-1$ players in $S$. Otherwise, call it "bad". (i) There is at least one tie. Assume $P$ tied with $Q$. If there are $m-2$ players who lost to $P$, then these players with $P$ and $Q$ form a bad set. So there are at most $m-3$ players who lost to $Q$. Similarly, there are at most $m-3$ players who won are tied with $P$. Thus there are at most $m-3+m-3+2=2m-4$ players, a contradiction. (ii) There are three players $P,Q,R$ such that $P$ won against $Q$, $Q$ won against $R$, and $R$ won against $P$ (call this a cycle). Similar as case (i), we find that at most $m-4$ players lost against $P$ and at most $m-4$ players won against $P$. Hence there are at most $m-4+m-4+3=2m-5$ players, a contradiction. (iii) There is no tie and no cycle. There is a player $P$ with the largest number of wins. If $Q$ won against $P$, then $Q$ beat all players who lost against $Q$, so $Q$ has more wins, a contradiction. So $P$ won against all other players. Among players other than $P$, there is a player who won against all other players. Continuing this, we can label the players as $P_1,P_2,\ldots,P_n$ such that $P_i$ won against $P_j$ for all $i>j$. Clearly their final scores are ditinct. So for $n\ge2m-3$, the result holds. Now we give a construction to show that $2m-4$ is not enough: $P_1,P_2,\ldots,P_{2m-4}$ are such that $P_i$ won against $P_j$ for all $i>j$, except that $P_{m-1}$ tied with $P_{m-2}$.