In some cultures, it is typical for guests at an event to shake hands when they meet other guests (when there isn’t a pandemic). Some might be more social and shake hands with a lot of other guests, while others may be less social and shake hands with few or no other guests.
Can you prove that, regardless of the number of guests at the event, there must be at least two guests with the same number of handshakes at the event? In other words, can you prove that it is impossible for every guest to have shaken a different number of hands?
Assume guests can’t shake hands with themselves.
Solution
Let’s say there are n guests:
- Any guest could shake hands with 0 other guests, 1 other guest, 2 other guests, etc. all the way up to n – 1 other guests (n handshakes is not possible because guests can’t shake hands with themselves).
- So far, we just know there are n possible numbers of handshakes, and n guests.
- However, it is not possible for there to be both a guest that shook hands with 0 other guests AND a guest that shook hands with n – 1 other guests.
- To shake hands with n – 1 other guests means that guest shook hands with every other guest, which means it is impossible for there to be a guest that did not shake any hands.
- This means there are only n – 1 possible numbers of handshakes.
- By applying the pigeonhole principle, we have proven that n – 1 possibilities spread across n guests means it is impossible for all n guests to have a different number of handshakes.
Want a harder challenge? Try this more difficult handshake puzzle.