Question

Prove that at any time, the total number of persons on the earth who shake hands an odd number of times is even.

Answer 1

To prove the assertion, we first assign to each hand shake a number in natural order. Then our assertion is equivalent to the following : "For every n, after a handshake with number n, the number of people who have made an odd number of handshake is even." This statement depend on n and will be prove by induction. For convenience, we we call the people who have made an odd number of handshake type A and rest type B, that is, type B are those people who had made an even number of handshakes.
After the handshake with number 1, we have two people of type A, an even number. After a mth handshake, let let the number of people of type A be even and let the handshake number m + 1 take place. Three cases arise : the handshake number m + 1 will occur between (a) two people of type A (b) two people of type B, (c) a person of type A and type B.
In case (a), two person of type A add one handshake to their odd number handshakes and becomes of type B; in case (b) two person of type B become of type A and in case (c) a person of type A becomes of type B and person of type B is changed into type A. Thus the number of people of type A either decrease by two or increase by two or remains unchanged. In any case the number remains even and the proof is complete