Math 110

The Hard Handshake Problem


  Problem:  A couple hosts a party for three other couples, so there are a total of eight people at the party.  When people arrive, they start shaking hands.  Not everybody shakes everyone else's hand.  In fact:
  • Nobody shakes hands with his or her partner, and
  • Nobody shakes his or her own hand.

So, the MOST hands anyone could shake is 6, and, of course, the least might be zero.

After all the hand shaking is over, the host asks the seven other people and finds

  • They have each shaken a different number of hands.

How many hands did the host shake?

One way to start:

The host got seven different answers from seven different people.  There are only seven different possible answers, 0, 1, 2, 3, 4, 5, 6, and so every answer had to be used.  Somebody shook 6 hands, someone else shook 0 hands.

Let's call the host H, and the host's partner HP.  Let's call the guests A1, A2 for the first couple, B1, B2 for the second and C1, C2 for the third.

Draw eight spots, arranged in a circle, to represent these eight people.

Now, somebody shook six hands.  You can't tell who.  If you don't have any idea what to do next, take a guess, and follow your guess.  (Remember, if you have to guess when solving a problem, it often means that there may be more than one solution.)

I'll guess B2 shook 6 hands. 

  • B2 didn't shake B1's hand.
  • B2 didn't shake his or her own hand.
  • B2 shook 6 hands.
  • Therefore, B1 shook hands with H, Hp, A1, A2, C1 and C2

Draw lines to represent these six handshakes.

Now, somebody shook zero hands.

Who could that be?  The only possibility remaining is B1.  So, we'll draw a little circle at B1 to remind us not to let him (or her) shake any more hands.  Let's draw one at B2, as well, for the same reason.

So far, we've taken care of the person who shook 6 hands and the person who shook 0 hands.  (But remember, this involved a guess, so it might not work out.)

Now, somebody shook 5 hands.  Do like we did before, and take a guess.  Say, guess that A1 shook 5 hands. 

  • A1 didn't shake hands with him- or herself.

  • A1 didn't shake hands with A2

  • A1 didn't shake hands with B1, because B1 is done shaking hands.

  • We already know that A1 shook hands with B2.

This means that A1 had to shake hands with everyone except: A1, A2 and B1.

Draw those lines.  Got the hang of it?  then

Continue until everyone is accounted for.

Another way to start:

Instead of trying to label people with their names, A1, A2, etc., we can refer to them by the number of hands they shook.  This way, people will be labeled H, 0, 1, 2, 3, 4, 5 and 6.

Start with Person 6.  That person

  • shook 6 hands

  • didn't shake his or her partner's hand

  • didn't shake his or her own hand

  • didn't shake hands with Person 0

Therefore, Person 0 is Person 6's partner, and we can draw the picture, as above, like this:

Now, three people are "full up," so we can add our little circles around People 0, 1 and 6:

Now, look at Person 5, and continue as before.

Reflecting, this way is a lot like the other way, but there is a quiet reason that it is a little better.  Can you figure out what that reason might be?



Hit Counter

created September 6, 2005