Readers still surprise me. I frequently offer challenges. Sometimes they get no responses, and sometimes my inbox is filled. In the last posting, I presented a puzzle submitted by Allen:

John and his wife, Mary, went to a dinner party with four other married couples. Because everyone didn’t know everyone else, there were the usual introductions and handshakes when the five couples gathered at the table.

As it turns out, each person did shake hands with every person they did not already know, but did not shake hands with anyone else they already knew, including their own spouses, of course.

At the end of the dinner, John asked everyone, “With how many different people did you shake hands?” All answered truthfully and each gave him a different number: 0, 1 ,2, 3, 4, 5, 6, 7, and 8.

Allen heard this puzzle on a radio show, so we assume it is for general consumption. Since the puzzle can be solved in several ways, I expressed an interest in what approaches were successful. A lot of you access Lockergnome over RSS because I started to get responses before the article appeared normally.

For those of you who might not have seen this before, take a few moments to consider it before looking at the answers. Actually solving this puzzle is quite rewarding because it is one of those delightful gems that looks impossible at first due to the limited information given, but which has a straightforward iron-tight logical solution.

Of course, some people, like Bert Bakker decided that Mary and the others all shook hands 8 times and anyone who said otherwise was lying. Nice try.

Here is a succinct solution from Bern Muller:

Well, I succumbed to the brute force method to solve this, and it took only a minute or so. But even that required an insight: The person who shook hands with 8 had to shake hands with 1 and with everybody except 0. and the person who shook 7 with everybody except 0 and 1, etc. This quickly showed that John shook 4 hands.

Now another insight: 8 had to be married to 0, 7 to 1, etc. This left John married to 4. So Mary shook 4 hands.

And a more elaborate version from David D:

Ten people were present, and we have replies from everyone (including Mary) other than John.

Mary cannot be the 8, because we know she did not shake Johns’s hand (spouse rule) and that would mean she shook hands with every other person who replied. That’s impossible because someone answered 0.

Could she be the 0? Someone other than John shook 8 hands, meaning everyone other than their spouses. Therefore both John and Mary must have shook at least one hand. John also could not have shaken 8 hands, because we now know that someone other than Mary shook 0.

Hmm, so the people answering 8 and 0 are spouses. Will we discover every other couple is similarly complimentary? I.E., 7 & 1, 6 & 2, 5 & 3, and 4 &… John? Meaning 4 is also Mary’s answer? It would be elegant and could be the expected flash of insight, but we’re not sure yet.

Well let’s look at the possibility of Mary having shaken 7 hands. Out of 9 possible handshakes, we know she didn’t shake John’s (spouse rule) or person 0’s. That would mean she shook everyone else’s hand though, including person 1’s. However, that’s not possible – person 1 must have shaken 8’s hand as well.

To reiterate, person 7 shook the hands of everyone except their spouse and person 0, but could not have shaken the hands of person 1, who must therefore be their spouse.

Applying this same reasoning, person 6 will have shaken the hands of everyone but person 0, 1 and their spouse, who we’ll find out is person 2.

Person 5 will have shaken the hands of everyone but person 0, 1, 2 and their spouse, who will be person 3.

Person 4 will have shaken the hands of everyone but 0, 1, 2, 3 and their spouse, who will be John, making person 4 Mary.

Other people submitted similar solutions. No one started the way I did buy observing that since it takes two people to shake hands, the number of odd handshakes must be even. Therefore John must shake hands an even number of times. Them with a few minutes of thought, the total shakes by spouses must be correlated such that Mary’s shakes must also be even. We can also quickly eliminate 0 and 8 as above, leaving only 2, 4, and 6 as candidates. Of these, one 4 is “special” and so is a candidate for proof by verification (i.e. guessing and then verifying) rather than derivation.

No matter how you do it, this is a great puzzle. Now does it generalize to N couples? Or does it matter if N is odd or even? What do you think?

For those who wish to delve further into decision theory without wading through a lot of equations, I have posted a tutorial on elementary decision theory. It shows examples of faulty physicians’ diagnoses (important for those considering surgery) and how to evaluate anti-terrorist activities (important for everyone). That tutorial can be found here.