Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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/
```
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search