Odd Number of Hands, Even Number of People

Date: 08/31/2001 at 18:57:12
From: Telinda
Subject: Logic/puzzles

Every person on earth has shaken a certain number of hands. Prove that 
the number of persons who have shaken an odd number of hands is even.

I have played with n and n-1 from the more classic handshake problems, 
but they do not seem to apply.  I am now starting down the road that 
for every 1 handshake there are two people involved. Is it that easy, 
that for any number of handshakes a multiple of two people is 
involved?

Date: 09/19/2001 at 17:07:38
From: Doctor Ian
Subject: Re: Logic/puzzles

Hi Telinda,

Start with the smallest positive number of handshakes:

  o.....o

In fact, the number of people who have shaken an odd number of hands 
is even. So far, so good.  Now add a handshake:

  o.....o
  .
  .
  o

As before, two people have shaken an odd number of hands. From now on, 
we have two ways to add a handshake: (1) add another person, or 
(2) add a handshake between two people who haven't yet shaken hands.  

Also, for brevity, let's let K stand for the number of people who have 
shaken an odd number of hands. 

In case (1), the new person has shaken one hand, so K increases by 1. 
What about the person he shakes hands with? If that person had 
previously shaken an even number of hands, now he's shaken an odd 
number, so K increases by 1 again. So if K was even before, it's even 
again:

  K is even -> K + 2 is even

If that person had previously shaken an odd number of hands, now he's 
shaken an even number of hands, so K decreases by 1.  So if K was even 
before, it's even again:

  K is even -> K + 1 - 1 is even

I'll let you chase down the details of case (2).  

Does this help? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/