Friday Math Solution

Solution to last week's problem: 10.

Formal solution by induction, as follows:

For each positive integer n, define P(n) to be - If the host invites n couples, and if no one shakes hands with his or her partner, and if each of the 2n+1 people interrogated by the host shook a different number of hands, then the hostess shook n hands.

First, check that P(1) is true by drawing a diagram and working out the only logical possibility. Next show that P(n) implies P(n+1).

So assume that P(n) is true. Now consider a party with n+1 couples (other than host and hostess) satisfying the hypotheses (no one shakes with partner; 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 questioned 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 partner.

Next, remove X and Y from the party. If we don't count handshakes involving these two people, we are reduced to a party with n invited couples, and everyone’s handshake number has dropped by exactly 1, since everyone shook hands with X and no one shook hands with Y. But the inductive hypothesis P(n) tells us that the hostess at this “abridged” party shook n hands. But in reality, the hostess shook one more hand—that of the X whom we just removed. So in the party with n+1 invited guests, the hostess shook n+1 hands, establishing P(n+1).