davidbau.com

Handshaking Puzzles

While you are going to holiday parties, you might want to count handshakes, because you will find some puzzling properties. Here are two handshaking puzzles.

Party Parity

Puzzle number one is from Shklarsky's USSR Olympiad Problem Book. It's a proof puzzle.

Why must an even number of people at any party shake hands with an odd number of others?

That is, if you count the number of people who have shaken hands with an odd number of people, the number will always be even...

The fun part of this puzzle is to actually test it out with any combination of handshaking. It is absolutely true!

Pair Party

The puzzling part of puzzle number two is that it is possible at all. Here it is:

You and your spouse invite ten other couples to a dinner party, and the partygoers shake hands with people they have never met before. At the end of the party (perhaps pursuing the parity problem) you ask everybody, including your spouse, to tell you how many people they shook hands with. Interestingly, everybody reports shaking hands with a different number of people. Of course, nobody shook hands with their partner.

The question is, with how many people did your spouse shake hands?

This puzzle, from Paul Zeitz's excellent The Art and Craft of Problem Solving, hinges on the fact that you don't ask yourself the question.

Heidi says, "of course your wife shakes everybody's hand, because she's the hostess," but it's not that kind of question. It's a math puzzle!

Posted by David at December 24, 2007 12:36 PM