Thread: number of handshakes in a party

A collection of couples attend a party at which a number
of people shake hands. Suppose that no pair shake hands more than once,
and no one shakes hands with her partner. At the end of the evening, the
host asks each of the other people how many hands they shook. She
receives different answers. How many hands did the host shake?

How many did her partner shake?

Originally Posted by sbankica

A collection of couples attend a party at which a number
of people shake hands. Suppose that no pair shake hands more than once,
and no one shakes hands with her partner. At the end of the evening, the
host asks each of the other people how many hands they shook. She
receives different answers. How many hands did the host shake?

How many did her partner shake?

Without even trying to hard the answer is use the pigeon hole principle! -- edit sorry this should say injectivity.

The answer is n-1. The logic used to it is rather tedious. Here is a quick overview.

There are 2n people. First, we must use injectivity. 2n-1 people reported 2n-1 different number of handshakes. Since the maximum number of handshakes is 2n-1-1 = 2n-2 a person can make, that means each persons number of handshakes is between 0 and 2n-2. Since there are 2n-1 values between 0 and 2n-2 we must have by injectivity that each person other than the hostess must have a unique number of handshakes between 0 and 2n-2. Label each person (other than the hostess) by their number of handshakes.

Consider person 2n-2, this person must have handshook everyone except 0, including the hostess. This is because there are 2n-1 possible people other than 2n-2 himself, but 0 is not available. Then consider person 2n-3 this person can not handshake 0 or 1 (1 has reached his maximum allowed handshakes) thus he must have handshook everyone except those 2. Continue this process until you reach person n this person must handshake everyone except people 0, ..., n-2. Now consider person n-1. This person has reached their exact allowed quota of handshakes already. This is true of all people n-1 to 0. Now consider the hostess. She can not be allowed to handshake any additional people for every person has reached their quota of handshakes. Thus she has handshook everyone from 2n-2 to n that is 2n-2 -n + 1 = n -1 people.

added the answer to my post above. Is should note by necessity her partner is person n-1. Thus both her and her partner shook n-1 hands.