logo
Interesting Math Problem   Math Problems Home  |  Home  |  Send Feedback

Combinations - Shaking hands

Prove that in a group of N people,
if some of them shake hands,
there are at least two who have the same number of handshakes.

Another handshake problem
This is easily proved using the "Pigeon Hole Principle", for example, here.

Here is a proof by induction:

Base:
First person enters the reunion.
Second person enters.
Either they shake or not, so either 0 0 or 1 1 shakes,
and there is a pair with same number of shakes.

Assume at any point, the condition holds.
Then there is at least one pair of equal shakes.

A new person can shake with both of them (keeps the parity),
neither of them (keeps the parity), or just one of them.

In the last case, the parity is broken for that pair
and the new person has 1 shake.

If there was another pair at parity, they remain at parity.
Otherwise, everyone but one pair had a different number of shakes.

If there were N people, that's N-1 numbers (which is
the maximum number of shakes).
So the numbers must have been 0, 1, 2, ...., N-1.
(with one missing and one duplicated).

If the pair had 1 shake, now one of them still does,
as does the new guy.

If the pair had a different number, then
either there was a 1 (someone else) who now matches
the new guy, or the member of the pair now matches
someone who had one more shake than he did (or both).

So in all cases, adding person (N+1) to the group,
if there was a pair at parity, there will still be a pair,
either the same or different.

Since it is true for 2, by the induction principle,
it is true for all N.

Here is a breakdown of the induction step:
Assume there's a pair.

Next shake(s) is with both of them: they remain at parity.
Next shake is with neither of them: they remain at parity.
Next shake is with one of them:

Example: 3 people, 4th is added: