Halmos's Handshake Puzzle - Answer

The beautiful thing about his puzzle is that it seems at first that there can't possibly be enough information to solve it. But there is.

Let's start by considering the person who shook 8 hands -- call this person A. Whose hands did A shake? Necessarily, A shook hands with everyone else present, apart from his or her spouse. So everyone besides A's spouse shook at least one hand, namely, A's hand.

So who is the person who shook 0 hands? Everyone but A's spouse shook at least one hand, so the person who shook 0 hands must be A's spouse. Let's call that person B.

Now consider the person who shook 7 hands, whom we'll call C. C didn't shake hands with him or herself, or with his or her spouse, or with B (because B shook no hands). That leaves only 7 other people, so C shook hands with everyone else, excepting B and his or her own spouse. And all of these people also shook hands with A, so all of these people shook at least two hands -- A's and C's. So the only person left who could have shaken just 1 hand is C's spouse (to be called D). So just as the person who shook 8 hands is married to the person who shook 0 hands, the person who shook 7 hands is married to the person who shook 1 hand.

Similar analysis applies to the person who shook 6 hands, E, who cannot have shaken hands with him or herself, his or her spouse, B (who shook 0 hands), or D (who shook only A's hand). So E shook hands with everyone else, and since they also shook hands with A and C, the only person left who could have shaken just 2 hands is E's spouse.

And applying the same logic one more time shows that the person who shook 5 hands is married to the person who shook 3 hands.

So the point is that the people who gave the answers 0, 1, 2, 3, 5, 6, 7, and 8 are all married to other people who answered Halmos's question. The only person who is not married to one of the people who answered a query from Halmos is the person who answered 4 -- and that must be Halmos's wife.

So Halmos's wife shook 4 hands -- and, it follows, Halmos did too.