In a school tennis tournament with $ m \ge 2$ participants, each match consists of 4 sets. A player who wins more than half of all sets during a match gets 2 points for this match. A player who wins exactly half of all sets during the match gets 1 point, and a player who wins less than half of all sets gets 0 points. During the tournament, each participant plays exactly one match against each remaining player. Find the least number of participants m for which it is possible that some participant wins more sets than any other participant but obtains less points than any other participant.
Problem
Source: Juniors Problem 3
Tags: inequalities, combinatorics unsolved, combinatorics
04.08.2008 05:30
The answer is 6. First, we give a construction: Players are A, B, C, D, E, F. All matches are ties, except the following: A4-B0 A4-C0 A1-D3 A1-E3 A1-F3 B3-C1 B3-D1 C3-E1 C3-F1 The resulting scores of the players in the form Player(points, sets) are A(4, 11), B(6,10), C(5, 9), D(5,10), E(5, 10), F(5, 10), so player A has the desired property. Now, suppose player X has the desired property, that X loses to $ a$ players, defeats $ b$ players and ties $ t$ players. In any such situation, we may adjust the final scores so that X wins 4 sets whenever he wins and wins 1 set whenever he loses without changing our desired properties, so we have that X wins $ a + 4b + 2t$ sets and $ 2b + t$ points. Thus every other player wins fewer than this many sets but more than this many points. It's easy to compute the total number of sets and points won by all other players, and doing so gives us the two inequalities \[ 4\binom{a+b+t}{2} + 3a + 2t < (a + 4b + 2t)(a + b + t)\] and \[ 2\binom{a + b + t}{2} + 2a + t > (2b + t)(a + b + t).\] Expanding these out and combining like terms gives \begin{align*} a^2 + at + a & < 2b^2 + ab + 2bt + 2b \\ a^2 + at + a & > b^2 + bt + b.\end{align*} From the second inequality it follows immediately that $ a > b$, while plugging $ a = 2b + c$ in to the expression $ a^2 + at + a - ab$ gives that $ a < 2b$. Since $ a, b$ are nonnegative integers, we must have $ b \geq 2$ and $ a \geq 3$ and so a total of at least $ 1 + 2 + 3 + 0 = 6$ participants.