76 CHAPTER (^3) TACTICS FOR SOLVING PROBLEMS
Po
It is interesting to look at the two people with the extreme handshake numbers, i.e.,
Po and P 4. Consider Po, the "least gregarious" member of the party. He or she shook
hands with no one. What about the "most gregarious" person, P 4? P 4 shakes hands
with everyone possible, which means that everyone except fo r P 4 ' s partner shook P 4 's
hand! So everyone who is not P 4 's partner has a non-zero handshake number. So P 4
and Po must be partners!
At this point, we can relax, for we have achieved the crux move. Our instinct tells
us that probably P 3 and PI are also partners. How can we prove this? Let's try to adapt
the argument we just used. P 3 shook hands with all but one person other than his or
her partner. PI only shook hands with one person. Do we have any more information?
Yes: P 4 was the one person that PI shook hands with and one of the people that P 3
shook hands with. In other words, ifwe exclude P 4 and his or her partner, Po, then PI
and P 3 play the role that Po and P 4 played; i.e., they are respectively the least and most
gregarious, and by the same reasoning, must be partners (P 3 shakes hands with two out
of the three people PI ,P 2 , H, and we know that PI doesn't shake hands with P 3 , so the
only possible person P 3 can be partnered with is PI).
Now we are done, for the only people left are P 2 and H. They must be partners,
so P 2 is the hostess, and she shakes hands with two people. It is easy to adapt thisargument to the general case of n couples.
Formal Solution: We shall use induction. For each positive integer n, define the
statement P(n) to be
If the host invites n couples, and ifno one shakes hands with his or her
partner, and if each of the 2n + I people interrogated by the host shook
a diff erent number of hands, then the hostess shook n hands.
It is easy to check that P( 1 ) is true by drawing a diagram and working out the only
logical possibility. We need to show that P( n) implies P( n + 1), and we'll be done. Soassume that P(n) is true for some positive integer n. Now consider a party with n+ 1
couples (other than host and hostess) satisfying the hypotheses (no one shakes withpartner; all handshake numbers are different). Then all handshake numbers from 0 to
2(n + 1) = 2n + 2 inclusive will occur among the 2n + 3 people interrogated by the
host. Consider the person X, who shook the maximum number of 2n + 2 hands. This
person shook hands with all but two of the 2n + 4 people at the party. Since no one
shakes hands with themselves or their partner, X shook hands with everyone possible.
So the only person who could be partnered with X had to have been the person Y, who
shook zero hands, for everyone else shook hands with X and is hence ineligible as a