Maximum Handshakers in a Room
A room has $N > 3$ people. You're told that at least one person in the room has not shaken hands with every other person. (Handshakes are symmetric -- if $A$ shakes $B$'s hand, then $B$ has shaken $A$'s hand.)
What is the maximum number of people who could have shaken hands with every other person in the room?
Find the answer when $N = 50$.
Hints
- Think of the handshake relationships as a graph. What does it mean for a person to have shaken hands with everyone?
- Handshakes are symmetric: if person $A$ hasn't shaken $B$'s hand, then $B$ also hasn't shaken $A$'s hand. How many people does one missing handshake disqualify?
- The constraint forces at least one non-universal person. Their missing partner is also non-universal. Can everyone else be universal? Try to construct such a configuration.
Worked Solution
How to Think About It: Think of the people as nodes in a graph and each handshake as an undirected edge. A person who has shaken hands with everyone else is a node of degree $N - 1$ -- a "universal" node. The constraint says at least one person is *not* universal, i.e., they are missing at least one edge. The question is: how many universal nodes can coexist with that constraint?
Quick Estimate: The constraint only forces at least one non-universal person. If person $A$ is missing a handshake with person $B$, then both $A$ and $B$ fail to be universal (since handshakes are symmetric). So the constraint knocks out at least 2 people. Everyone else -- the remaining $N - 2$ -- could in principle have shaken hands with all $N - 1$ others. For $N = 50$, that gives at most $48$. Quick gut check: can we actually build such a configuration? Yes -- so $48$ should be the answer.
Approach: Construct an explicit handshake graph achieving the bound and verify no better configuration exists.
Formal Solution:
Label the people $1, 2, \ldots, N$. The constraint guarantees at least one non-universal person; call them person $1$. Since person $1$ is non-universal, there exists some person $2$ such that $1$ and $2$ have not shaken hands.
Now observe: - Person $1$ is missing the handshake with person $2$, so person $1$ is not universal. - Person $2$ is missing the handshake with person $1$ (by symmetry), so person $2$ is not universal. - That accounts for at least $2$ non-universal people.
Can the remaining $N - 2$ people all be universal? Yes. Construct the following graph: - Persons $3, 4, \ldots, N$ each shake hands with every other person in the room (including persons $1$ and $2$). - Person $1$ shakes hands with everyone except person $2$. - Person $2$ shakes hands with everyone except person $1$.
In this configuration, persons $3$ through $N$ each have degree $N - 1$ (they shook hands with all $N - 1$ others), so they are all universal. Persons $1$ and $2$ each have degree $N - 2$, so they are not universal. The constraint is satisfied.
Can we do better than $N - 2$? No. If there is at least one non-universal person, their missing handshake partner is also non-universal. So at least $2$ people are non-universal, and the maximum number of universal people is $N - 2$.
Answer: The maximum number of people who have shaken hands with every other person is $N - 2$. For $N = 50$, the answer is $\boxed{48}$.
Intuition
The key insight is that handshakes are symmetric, so a single missing handshake always disqualifies exactly two people from being universal. The constraint says at least one person is non-universal, but that person's missing partner is automatically non-universal too -- you can never have just one non-universal person. Beyond those two, nothing stops everyone else from shaking hands with the entire room, including the two "deficient" people.
This is really a graph theory observation dressed up in a social setting. In graph language, you're asking for the maximum number of universal vertices (degree $N-1$) in a graph on $N$ vertices where at least one vertex is not universal. The complement graph must have at least one edge, and every edge removes two vertices from the universal set. It's a nice example of how symmetry constraints (here, the undirectedness of handshakes) can force stronger conclusions than you might initially expect.