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$
Problem
Source: 17-th Iranian Mathematical Olympiad 1999/2000
Tags: combinatorics proposed, combinatorics
06.05.2024 10:51
"Only If" direction is simple. Since $\sum d_x$ of $X$ is sum of all matches that one of vertice in $X$ is won, it must at least all edges in $X$. And if $X$ is total set, every edge is in $X$ and equality holds. So condition $1$, $2$ holds. Harder part is "if" part. We use induction on number of edges($k$) to prove it. Base case $k=1$ is trivial, since there is only one edge $e=\overline{uv}$ and only one of $u$, $v$ has $d=1$. Other vertice has $d=0$, so if we just orient $e$ to direction of vertice having $d=1$ we're done For the case $k$ edges, pick one edge $e=\overline{uv}$. Let's define $E(X)$ as number of edges in set $X$, $E(X, Y)$ as number of edge between two disjoint set $X$, $Y$. And let's call set $X$ is wicked if $ \sum_{A_j\in X}d_j=E(X)$. We use the following claim; Claim. There exist vertex $w$ of $e$ such that every set $X$ containing $w$ but not containing $e-w$ is not wicked(in other words, $ \sum_{A_j\in X}d_j>E(X)$. Proof. Suppose not. There exist set $S$ that not containing $u$ but $v$, and $T$ that not containing $v$ but $u$, and both sets are wicked. Think about quantity $E(S)+E(T)$. It counts all edges inside $E(S \cup T)$ but edges between $S-T$ and $T-S$, and all edges inside $S \cap T$ is counted twice. So it means $E(S)+E(T)=E(S \cup T)+E(S \cap T)-E(S-T, T-S)$. And since $v \in S-T$ and $u \in T-S$, $e \in E(S-T, T-S)$. So $|E(S-T, T-S)| \geq 1$, and inequality $E(S)+E(T)<E(S \cup T)+E(S \cap T)$ follows. But by condition $2$, right side is at most $\sum_{A_j\in S \cup T}d_j+\sum_{A_j\in S \cap T}d_j$. And since this is equal to $\sum_{A_j\in S}d_j+\sum_{A_j\in T}d_j$, we get contradiction because this is same as left side since $S$, $T$ is wicked. By our claim, there exist such vertex $w$. Let's erase $e$ and define sequence $d'_x$ as $d'_x=d_x-\delta_{x, w}$ where $\delta_{x, w}$ is kronecker delta. Then, surprisingly, we get new graph having $k-1$ edges and sequence $d'_x$ satisfies two condition. Let's prove it. Condition $1$ holds trivially. If set $X$ contains both $w, e-w$ or not contain both of them, it's $\sum d_x$ and $E(X)$ is both decreased by $1$ or unchanged. So it satisfies condition $2$. And if $X$ only contains $e-w$, it's $\sum d_x$ and $E(X)$ is unchanged so condition $2$ holds. Finally, if $X$ only contains $w$ then it's $\sum d_x$ is decreased by $1$ and $E(X)$ remains unchanged, but all of this $X$ is not wicked by claim, so condition $2$ also holds. So use induction on new graph and add $e$. And let's orient it to direction $w$ exists. It's easy to see that this graph is what we're looking for!