Interactive proof

At least two guests must shake the same number of hands

There are 26 people total: you and 25 other guests. You shake hands with all 25 guests. We want to show that among those 25 other guests, at least two must have shaken hands with the same number of people.

1) Ignore your handshakes first

Since you shake hands with everyone, each of the 25 guests gets an automatic +1 to their total. So it is enough to look only at handshakes among the 25 guests themselves.

25 guests to analyze
Possible counts: 0 to 24
Need to force a duplicate
YOU
You
Each of the 25 guests
A handshake from you

2) Possible handshake counts

For the 25 guests, a person could shake hands with 0, 1, 2, ..., 24 of the other guests. That looks like 25 possible values.

3) Apply the pigeonhole principle

Now we compare the number of people (pigeons) with the number of available handshake counts (holes).

25
guests = pigeons
25?
possible counts = holes
?
comparison