Party Handshake Counts Guaranteed

This brain teaser is set at a social gathering where everyone is shaking hands with one another in some arbitrary pattern. You are told nothing about the detailed sequence of handshakes or how sociable any particular guest is; instead, you are asked whether you can still guarantee that two attendees end up with exactly the same handshake count. The charm of the question is that it looks like it should depend on the actual interactions, but in fact it only relies on counting how many different handshake totals are even possible in such a room.

To answer it, a candidate must recognize the constrained range of handshake counts in any mutual-handshake setting and translate that into a simple counting argument. The key technique is the pigeonhole principle applied to degree counts in a complete-undirected-graph framework. Interviewers watch for someone who can strip away irrelevant detail, identify the true combinatorial structure, avoid off-by-one errors about possible counts, and articulate a clean, general argument rather than resorting to ad hoc case-checking.

What it tests

Whenever you have a set of objects (like people) and assign to each a value from a limited set of possibilities (like the number of handshakes), the pigeonhole principle tells you that if there are more objects than possible values, at least two objects must share a value. In handshake problems, the possible number of handshakes for each person is constrained by the group size and the rules (no one shakes their own hand, and handshakes are mutual). This means the set of possible handshake counts is always one less than the number of people, so with $n$ people, there are only $n-1$ possible handshake counts. The principle holds because you cannot distribute $n$ distinct labels among $n$ people without repeating at least one label if there are only $n-1$ labels to use.