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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.