3.4 INVARIANTS 95Example 3.4.7 If 127 people play in a singles tennis tournament, prove that at the
end of tournament, the number of people who have played an odd number of games is
even.
Solution: Many people unsuccessfully approached this problem by assuming that
the tournament had a particular structure , such as double-elimination or round-ro bin,
etc. But the problem doesn't specify this! The implication is that no matter how the
to urnament is structured the number of people who have played an odd number of
games must be even. For example, one possible tournament would be one where no
one plays any games. Then the number of people who have played an odd number of
games is zero, which is even, as required.
There seem to be very few restrictions. Are there any? Yes, each game has exactly
two people playing in it. In other words, if A plays with B then that game is counted
twice: once as part of A's count, and once as part of B's count. More precisely, if we
let gi denote the number of games that player i has played at the end of the tournament,
then the sum
g l + g 2 + g 3 + ... + g (^127)
must be even, since this sum counts every game that has been played exactly twice!
Notice that this sum is always even, not just at the end of the tournament, but at any
time!
Now we are done; the sum above is even, and is a sum of an odd number (127)
of elements. If an odd number of them were odd, the sum would not be even. So the
number of gi that are odd is even. _
The next problem came from a 1906 Hungarian contest. We shall present two so
lutions; the first uses parity in a straightforward way and the second cleverly constructs
another invariant first.
Example 3.4.8 Let al ,a 2 , ... ,an represent an arbitrary arrangement of the numbers
1,2,3, ... , n. Prove that, if n is odd, the product
(al - l)(a 2 - 2 )(a 3 - (^3) )··· (an -n)
is an even number.
Solution 1: It is helpful, of course, to look at a concrete case, say, n = 11. Em
ploying the penultimate step strategy, we ask ourselves, what will force the product
(al - (^1) )(a 2 - (^2) )(a 3 - (^3) )··· (all - (^11) )
to be even? Clearly, it is sufficient to show that one of the numbers
al - (^1) ,a 2 - 2,a 3 - (^3) , ... ,all - 11
is even. How to do this? A good strategy is to try a proof by contradiction, since we
need to show that just one of the numbers above is even, and we don't know which
one. But if we start with the assumption that all of the numbers are odd, we have nice
specific information to work with. So assume that each of
al-l,a 2 - 2 ,a 3 - 3 , ... ,all - ll