In a chess tournament, every participant played with each other exactly once, receiving $1$ point for a win, $1/2$ for a draw and $0$ for a loss. (a) Is it possible that for every player $P$, the sum of points of the players who were beaten by P is greater than the sum of points of the players who beat $P$? (b) Is it possible that for every player $P$, the first sum is less than the second one?
Problem
Source: ToT - 2001 Spring Senior A-Level #5
Tags: combinatorics unsolved, combinatorics
17.08.2011 16:39
I don't think so for both. We can just ignore the fact that there are draws. Now we draw a directed graph, with vertices represent players and edges $a\to b$ if b beats a. For every player $p$, consider the first sum minus the second sum. If we sum them all for every player, the value is 0. So it is impossible for it to be positive or negative.
19.08.2011 02:02
I don't think that oneplusone's sum is always 0. Let $n$ be the number of players and let $G$ be the directed graph representing wins and losses. Then the player corresponding to vertex $v$ in $G$ receives $points(v)=\frac{1}{2}(n-1+deg^+(v)-deg^-(v))$ points. Now oneplusone's sum $S$ is \begin{align*} S&=\sum_{v \in G}\left(\sum_{vw \in E(G)}points(w)-\sum_{wv \in E(G)} points(w)\right)\\ &=\sum_{w \in G} points(w)(deg^-(w)-deg^+(w))\\ &=\frac{n-1}{2}\sum_{w \in G}(deg^-(w)-deg^+(w)) - \frac{1}{2}\sum_{w \in G}(deg^+(w)-deg^-(w))^2\\ &=- \frac{1}{2}\sum_{w \in G}(deg^+(w)-deg^-(w))^2\\ &\leq 0 \end{align*} Therefore, this method discounts only one of possibilities (a) and (b). (Side question: is there a direct combinatorial or probabilistic way to see that the sum is never positive?)