Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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".)

share|improve this question
1  
There isn't much to 'get'. This question is used to introduce the idea of double counting, i.e that $\sum w_i = \sum l_i$. While that is obvious, it is slightly surprising that $\sum w_i^2 = \sum l_i ^2$. Note that we need not have $ \sum w_i ^3 = \sum l_i ^3 $. –  Calvin Lin Sep 20 '13 at 0:27
1  
I have fond memories of this question: it was on the Putnam that I took my freshman year, and it was one of several questions that I solved. –  Brian M. Scott Sep 20 '13 at 0:29
    
Related: math.stackexchange.com/questions/6873/… –  Aryabhata Sep 20 '13 at 1:31

2 Answers 2

up vote 14 down vote accepted

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.

share|improve this answer
    
Brian, why do you say (or imply) that the proof I gave is unclear? Not illuminating $\neq$ unclear, to me. –  Chris Sep 20 '13 at 0:29
    
@user1296727: Because it is. It’s worded so as to obscure what’s going on. –  Brian M. Scott Sep 20 '13 at 0:31
    
Out of curiosity: how would you reword it? (I treated a small case with the opposite intent.) –  Chris Sep 20 '13 at 0:31
    
@user1296727: As in my answer, though on the exam itself I’d probably omit the last sentence. –  Brian M. Scott Sep 20 '13 at 0:33
    
Actually, when I read your answer, that basically answers that question. I think you've got a slight typo: your fifth line of math should be equal to $0$. –  Chris Sep 20 '13 at 0:33

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.