Handshakes at a Party
100 guests go to a party and some of them shake hands with each other. Show that there are two guests who handshake the same number of people.
SOLUTION
Each of the people at the party has shaken hands between 0 and 99 times. However, if someone has shaken hands 0 times (with nobody), it is impossible that another one has shaken hands 99 times (with everybody). Therefore there are at most 98 different options for the number of handshakes at the party, and thus two of the guests have shaken hands the same number of times.
We do not know where this puzzle originated from. If you have any information, please let us know via email.