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:
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
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.
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.
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
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?
created September 6, 2005