1965 Putnam, B2

The problem statement:

Suppose $n$ players engage in a tournament in which each player plays every other player in exactly one game, to a win or a loss. Let $w_i$ and $l_i$ denote the wins and losses of the $i$th competitor, $i = 1, 2, ... n$. Prove that $\sum {w_i}^2 = \sum {l_i}^2$.

A rather un-illuminating proof of this is the following (WLOG we treat $n= 4$):

Each player has exactly $4-1 = 3$ wins and losses total, so $w_i + l_i = 3$, and there will be an equal number of wins and losses total as well (in fact, $4 \choose 2$). Thus

$${w_1}^2 - {l_1}^2 + {w_2}^2 - {l_2}^2 + {w_3}^2 - {l_3}^2 + {w_4}^2 - {l_4}^2 = 0$$ $$ \iff 3 (w_1 - l_1 + w_2 - l_2 + w_3 - l_3 + w_4 - l_4) = 0$$

which is true.

I wanted to ask: is there a combinatorial proof of this which explains it better? Something with pigeonholing? (This might be pointless, but I still don't "get" this problem. Perhaps there's nothing else to "get".)

Solution 1:

That ‘proof’ is perfectly awful. The easiest argument isn’t combinatorial, but it’s much clearer than that. First,

$$\sum_{k=1}^n\left(w_k^2-\ell_k^2\right)=\sum_{k=1}^n(w_k+\ell_k)(w_k-\ell_k)\;.$$

Each competitor plays $n-1$ matches, so $w_k+\ell_k=n-1$ for every contestant, and we have

$$\begin{align*} \sum_{k=1}^n\left(w_k^2-\ell_k^2\right)&=\sum_{k=1}^n(w_k+\ell_k)(w_k-\ell_k)\\ &=(n-1)\sum_{k=1}^n(w_k-\ell_i)\\ &=(n-1)\left(\sum_{k=1}^nw_k-\sum_{k=1}^n\ell_k\right)\;. \end{align*}$$

But the total number of matches won is obviously equal to the total number of matches lost, so

$$\sum_{k=1}^nw_k-\sum_{k=1}^n\ell_k=0\;,$$

and therefore

$$\sum_{k=1}^n\left(w_k^2-\ell_k^2\right)=0\;,$$

or

$$\sum_{k=1}^n\left(w_k^2=\ell_k^2\right)\;.$$

If you want, you can actually calculate that

$$\sum_{k=1}^nw_k=\sum_{k=1}^n\ell_k=\binom{n}2\;,$$

since there is one match for each pair of contestants, but it’s not necessary to do so.

Solution 2:

The accepted answer is fine, but here is another one.

Think of the result of the tournament as a directed graph, with an edge pointing from loser to winner of each game. $\sum w_i^2$ is the number of pairs of edges pointing into the same vertex. $\sum \ell_i^2$ is the number of pairs of edges pointing away from the same vertex. Both these configurations can be counted by looking at all possible triples of vertices, and then looking at the configurations of edges involving only that triple of vertices.

On a triple of vertices there are two possible configurations up to symmetry. The cyclic orientation contributes 0 to $\sum w_i^2$ and $\sum \ell_i^2$, while the acyclic orientation contributes 1 to each.

Thus the total sum is the same for both.