Handshakes at a Party

The Master of Trinity College and his wife invite n fellows and their wives to a party. During the party a fellow may shake hands with anyone except himself and his wife (assume all fellows are male, and that they'll only shake hands with someone once).

At the end of the party, the Master asks everyone else in the room how many people they shook hands with, and recieves 2n+1 different answers.

i) Show that the Master's wife didn't shake hands with the most people.

ii) How many hands does the Master shake?

Source: James Michael O'Driscoll, Ask NRICH web message board.

Before I give my (rather long-winded) solution, I must mention the case where n=0. In this case, either the master shook hands with his wife, or he didn't. In either case, part i is impossible, because the Master's wife did shake hands with the most people of anyone at the party, although she was not in sole possession of that title. If the master and his wife shook hands, then the answer to part ii is 1, else 0. 

Ahh, you may say, the master is a fellow, and as such he does not shake hands with his wife. If that's the case, then I plead ignorance of the titles of the lords and dukes of Trinity College. 

Now for the answer to the puzzle, which is nonambiguous, when n is at least 1. I assume the fellows are all married, or at any rate, that they all bring along a person whom they refer to as their "wife"... 

2n+2 people attended the party. Since no one shook his own hand or his spouse's, the largest answer to the master's question is 2n. Consider the person (other than the master) who shook 2n hands. That means he or she shook everyone's hand except his or her spouse's. So everyone other than the 2n-shaker's spouse shook at least 1 hand. The 2n-shaker's spouse, then, is the only person who shook 0 hands. Neither the master nor the master's wife could have shaken 2n hands, because if they did, they would have shaken the 0-shaker's hand. 

Now take the 2n-shaker and his spouse, the 0-shaker, out of the puzzle. 

Among those who remain, with their answers to the master's question adjusted to ignore having shaken the 2n-shaker's hand, the puzzle is this: There are k (where k=n-1) fellows and their wives at the party, along with the master and his wife, and the party-goers give 2k+1 different answers to the master's question. That means one person (other than the master) who shook 2k hands, and by the same reasoning as above, neither the master nor his wife could have shaken 2k hands. 

Notice that the puzzle, as adjusted to ignore one handshake on the part of each person at the party, is identical to the original puzzle. 

One by one, the largest hand-shaker and his or her spouse, the smallest hand-shaker, are removed from the puzzle until only the master and his wife remain. As each couple is ejected from the party, we are assured that one of them shook the hands of both the master and his wife, and the other shook the hand of no one who was then at the party, in particular neither the master's nor his wife's hand. 

When none of the invited guests remain (k=0), i.e. when n couples have been shown the door, both the master and his wife will have shaken exactly n hands. 

Related pages in this website

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]