Ponder This Challenge - June 1998 - Shaking hands in a party

Ponder This Challenge:

Four couples attended a party. One couple was you and your spouse; another was Pat and Chris. Some people shook hands with one another, but nobody shook hands with oneself or with one's own spouse.

After the party, you asked each person (except yourself) how many different people the person had shaken hands with. Each person replied with a different number--and each person's reply was truthful.

You shook hands with Pat. Did your spouse shake hands with Pat? With Chris?

Correct answers must also include an explanation of how you arrived at your answer.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  We begin with what we know: since nobody shook hands with more than six persons, and the seven people other than
  yourself all shook hands with a different number of people, the numbers must have been:
  0,1,2,3,4,5,6, respectively.

  Let us begin with "0"--whom we shall call the introvert, because this person shook nobody's hand. At the other extreme
  was "6"--whom we shall call the extrovert for obvious reasons. The extrovert shook everybody's hand, except his/her
  own spouse. Since the extrovert and the introvert did not shake hands, the introvert must be the extrovert's spouse.

  0&6 are a couple, leaving 1,2,3,4,5 and yourself

  Consider the remaining five people other than yourself. Each of these shook hands with the extrovert, and none with the introvert.

  One of these five people-- "1", the quasi-introvert--only shook hands with one other person, the extrovert. Another--
  "5", the quasi-extrovert--shook hands with five people, everyone except his/her own spouse and the introvert ("0").
  Therefore, the quasi-introvert and the quasi-extrovert form a couple.

  0&6, 1&5 are couples, leaving 2,3,4 and yourself.

  In the same way, "2" and "4" form a couple--we'll call them the pseudo-introvert and pseudo-extrovert, respectively.

  0&6, 1&5, 2&4 are couples, leaving 3 and yourself.

  Therefore, your spouse is the one who shook hands with three other persons. Furthermore, you and your spouse shook hands with the same people: the extrovert ("6"), the quasi-extrovert ("5"), and the psuedo-extrovert ("4"). This gregarious group includes Pat (one of our givens: you shook hands with Pat), and therefore must exclude Chris.

  Answer: Your spouse shook hands with Pat, but not Chris.

  Lloyd's Solution

  Bragging:
  The puzzle took me about 15 minutes to solve, and about two hours to lay out the solution in a coherent (I hope) manner. It isn't a world-shaking accomplishment, but these kind of puzzles usually frustrate me no end. I figured it would take days just to get the solution. So I've got a big head right now.

  My solution:
  My reasoning went as follows:

  1. Fact: There are 8 total people at the party.- The maximum number of other people anyone can shake hands with is 6. Eight minus two (can't shake with yourself or your spouse).- Everyone at the party shook hands with a different amount of people! This seems to lead to a contradiction. If nobody could press the flesh with more than 6 people, then how could 8 folks each shake hands with a different amount of people?

  BUT...someone might have shaken hands with no one at all. Antisocial, yes, but still a possibility.

  AND...not all 8 people must have a different number. According to the instructions, I ask everyone else how many friends they shook with, and everyone else replies with a different number. One of their numbers could be the same as mine. One repeat (and only one) is therefore allowed.

  These two nuances allow all the 7 possible handshake counts (6, 5, 4, 3, 2, 1, and 0) to be allocated to the 7 guests other than myself. Of course, at this point, we have no idea which number is the same as mine, but if you study probability, you can probably guess.

  OK, enough text. Let's draw a picture. It's an artist's rendition of 8 people at a party, each one next to his or her spouse.

  Now, Let's start with a person at random, call him Socialite Bob. Socialite Bob shakes hands with everyone except his spouse (So his total is 6 handshakes with different people).

  This gives everyone but Socialite Bob's spouse a handshake total of at least one, and Socialite Bob's spouse a handshake total of zero. We'll name her Antisocial Annie.

  We also know that no two guests can both have a handshake count of 6 or 0. (6 and 0 cannot be the repeating totals) If more than one person has zero handshakes, Socialite bob cannot have six. And if more than one person has six handshakes, Antisocial Annie cannot have zero.

  So...two down, six to go.

  One of the remaining guests must have five handshakes. Since everyone but Bob and Annie has exactly one handshake so far, we can pick someone at random. Call her Friendly Jill.

  Three down, five to go.

  OK, let's see. Friendly Jill shakes hands with everyone but her spouse and Antisocial Annie. That gives her the required handshake count of 5.

  And, hey! Everyone except Friendly Jill's spouse has a handshake count of two. That must mean that Friendly Jill's spouse gets the handshake total of one. We'll call him Bad-Breath Ernie.

  Four down, four to go.

  Now, we pick one of the four remaining people and add two more handshake lines, bringing that person's total to four. Of course, we can't interfere with our previous selections, and we can't draw the lines to a person's spouse, so we have to do it like this. We'll call this person Four-Shake Fred.

  Five down...

  It looks like Four-Shake Fred's spouse is two-shake Tammy.

  Click for the IBM techexplorer version.

  Good luck planning your next party.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers