Two Guests Who Shook the Same Number of Hands
You attend a party with your 25 teammates, so there are 26 people in the room. Every one of your 25 teammates shakes your hand. Beyond that, the teammates shake hands among themselves in some arbitrary pattern: any pair of teammates may or may not shake hands, and you do not get to see who shook hands with whom. No pair shakes hands more than once, and nobody shakes their own hand.
Without knowing anything about the pattern of handshakes among your teammates, can you be certain that there are two people in the room who shook exactly the same number of hands? Prove your answer.
Hints
- Count how many hands each person could possibly have shaken. Everyone shook your hand, so nobody has a count of zero.
- The largest possible count for any person is 25 (everyone else in the room). So every count lies in the range 1 to 25.
- There are 26 people but only 25 possible values, so by the pigeonhole principle two people share a count.
Worked Solution
How to Think About It: "Can you be certain" with no information about the pattern is a cue for a pigeonhole argument: identify the range of possible values (the holes) and compare it with the number of people (the pigeons). The one piece of structure you do have is that you shook hands with everyone, and that is what closes the gap.
Approach: Bound the possible handshake counts and count.
Formal Solution:
*Step 1 -- Model.* Represent the room as a graph with 26 vertices (you and 25 teammates), with an edge between two people if they shook hands. Each person's handshake count is the degree of their vertex.
*Step 2 -- Upper bound on degrees.* No one can shake more than 25 hands, since there are only 25 other people. So every degree is at most $25$.
*Step 3 -- Lower bound on degrees.* You shook hands with all 25 teammates, so your degree is exactly $25$, and every teammate shook at least your hand, so every teammate's degree is at least $1$. Hence every degree lies in $\{1, 2, \ldots, 25\}$.
*Step 4 -- Pigeonhole.* There are 26 people (pigeons) and only 25 possible degree values (holes). By the pigeonhole principle at least two people have the same degree, i.e. shook the same number of hands.
*Step 5 -- Why the assumption about you matters.* In a general graph on 26 vertices, degrees range over $\{0, 1, \ldots, 25\}$, which is 26 values, so pigeonhole does not apply directly. The classical fix is that $0$ and $25$ cannot both occur (a person who shook everyone's hand rules out a person who shook nobody's), which again leaves at most 25 values. Here the problem hands you that step: because you shook everyone's hand, the value $0$ is excluded outright.
Answer: Yes. Every one of the 26 people shook between 1 and 25 hands (nobody shook zero, since everyone shook yours), so 26 people share only 25 possible counts and two of them must have shaken the same number of hands.
Intuition
The handshake counts are the degrees of a graph on 26 vertices, and the fact that you shook everyone's hand removes the value 0 from the possible degrees. That squeezes 26 degrees into the 25 values from 1 to 25, and pigeonhole finishes it. The general fact (in any graph with at least two vertices, two vertices share a degree) rests on the same observation that 0 and $n - 1$ cannot both occur. Pigeonhole arguments of this kind are the fastest way to prove existence without construction, and they appear in interviews as a test of whether you count the holes correctly.