Welcome to NRICH.

 
Hand shaking problem
By Julian Pulman on Saturday, July 27, 2002 - 05:42 pm:

The Master of Regent's College and his wife invite n Fellows and their spouses to a party. After the party. After the party the Master asks everyone (including his own wife) how many people they shook hands with, and receives 2n+1 different answers. Of Course, no woman shook hands with her husband.

How many hands did the Master shake?

---

It's quite easy to show that the person who shook zero hands and the person who shook 2n hands are married to each other.
I'm quite sure that, given the set of answers {0,1,2,...,2n} the subset of answers which are given by the people who shook hands with the person who shook t hands is:
St={x|2n-t<x£2n}
ie, S0={2n} ..supporting my first statement that 2n and 0 must be married.
could I use this reasoning to show that the wifes and husbands are symmetrically distributed in the set, such that someone who shakes 3 hands is married to someone who shakes 2n-3 hands?
This means the master's wife shakes n hands...but what about the master?

Help!!

Julian

By Graeme Mcrae on Saturday, July 27, 2002 - 08:47 pm:

You're right about the symmetrical distribution, and I think your reasoning is sound. But s0={}, the empty set, by your definition. This is the way I would express it...

First, "2n" who shook 2n hands shook everyone's hand except person "0" who must be "2n's" spouse. "2n" must have shaken the Master's hand, and "0" couldn't have shaken it.

Now remove "2n" and "0" from the set of responses to the Master's question, and consider the answers that the other 2n-3 people would give if they exclude persons "2n" and "0". Since "2n" is removed from the set, the number of handshakes performed by everyone else is reduced by 1. Also, since "2n" and "0" and are removed from the set, the largest and smallest responses are removed. Thus you will see the responses to the Master's question (as amended to ignore these two responses) range from 0 to 2n-3.

So among the participants other than the Master, and the two we removed, we have the same situation: the responses to the question range from 0 to one less than the number of people who participated. So a person, "2n-2", shook everyone's hand but "2n-2's" spouse, who must have shaken zero hands.

Note that "2n-2" must have shaken the Master's hand, while the new "0" could not have shaken it.

Now peel "2n-2" and the new "0" off the set (like an onion), and then continue in this fashion until the set contains just one member, who must be the Master's wife because all the other spouse-pairs were removed.

Also, exactly one of each spouse pair that was removed had shaken hands with the Master. So the Master must have shaken n hands, just like his wife.

By Julian Pulman on Saturday, July 27, 2002 - 11:21 pm:

Great! I had this as a suspicion (if the set was symmetically distributed, the Master must be n, to conform with that requirement).

Thanks Graeme.

Julian