Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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,

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/   
    
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/