Last modified on 21 September 2008, at 00:45



Double CountingEdit



At a convention the number of delegates who shake hands at odd number of times are even.

To see this, let D_1,\cdots D_n be the delegates. Let x_i\, be the number of times D_i\, shakes hands and y\, the number of handshakes that occur. Clearly the total number of handshake pairs, or the total number of times hands were extended is


But counting another way it's just 2y\, for each handshake entitled two extended hands. So,


Now how many odd x_i\, can be there in the sum. If the number of odd x_i\, was odd then their total must have been odd too (say 2a+1). This when added to the sum of the even x_i\, (say 2b) would have given an odd number (2a+2b+1). But we just saw that \sum_{i=1}^{n}x_i was even. So the number of odd x_i\, was even. But that's just another way of saying that the number of delegates who shook hands an odd number of times was even.


(n+1)^2 = n+1+2S\,,


n(n+1) = 2S\,,


S = \sum_{k=1}^n{k} = \frac{n(n+1)}{2}.