Problem

Source: 17-th Iranian Mathematical Olympiad 1999/2000

Tags: combinatorics proposed, combinatorics



In a tennis tournament where $ n$ players $ A_1,A_2,\dots,A_n$ take part, any two players play at most one match, and $ k \leq \frac {n(n - 1)}{2}$ $ 2$ matches are played. The winner of a match gets $ 1$ point while the loser gets $ 0$. Prove that a sequence $ d_1,d_2,\dots,d_n$ of nonnegative integers can be the sequence of scores of the players ($ d_i$ being the score of$ A_i$) if and only if $ (i)\ \ d_1 + d_2 + \dots + d_n = k$, and $ (ii)\ \text{for any} X\subset\{A_1,\dots,A_n\}$, the number of matches between the players in $ X$ is at most $ \sum_{A_j\in X}d_j$