Are there at least two people present who shook hands with exactly the same number of people?

Question

The following is an interview question.

You are invited to a welcome party with $25$ fellow team members. Each of the fellow members shakes hands with you to welcome you. Since a number of people in the room haven't met each other, there is a lot of random handshaking among others as well. If you don't know the total number of handshakes, can you say with certainty that there are at least two people present who shook hands with exactly the same number of people?

I have a vague feeling that the answer is yes, which can be justified using the Pigeonhole principle.

However, I do not know how to answer the question concre

Answer 1

Proof by contradiction:

Assume that no one shook the same number of hands. That must mean that every possible number of hands shook from $0$ to $24$ occurs for exactly one person.

However, this is impossible, as one person shook $24$ hands, meaning he shook hands with everyone. But there is also someone who shook $0$ hands, shaking no one's hand.

Answer 2

It is pigeonhole with a twist, and has something to do with $26$.

Every person shook hands with at least one person, which is you. So if we classify people by the number of handshakes each person performed, then we have $26$ people and $26$ pigeonholes.

However, we rule out every pigeonhole being occupied by exactly one person.

Suppose this happened. Then the total number of handshakes performed by everybody is an even number, because handshaking is an event of pairs, and we count each handshake twice due to this. For example, if I (was your fellow team member and) shook hands with you, then it would count in your and my count, and so twice in the total count.

However, if each of $1,...,26$ were occupied by one person, then you'd get a total of $1+2+...+26 = \frac{26 \times 27}{2}$ handshakes, and that is an odd number, is $351$.

Thus, it follows that some pigeonhole has more than one pigeon, as desired.

Answer 3

This can actually be generalized into $n$ members instead of just $25$ members. We know that there can be $0,1,\cdots , (n-1)$ handshakes between these $n$ members. However, $0$ and $(n-1)$ handshakes can't appear both at once. So we're only left with $(n-1)$ possible number of handshakes among them. Since there are $n$ members, by the Pigeonhole Principle there must be at least two of the members having the same number of handshakes, as desired.