Various handshaking problems are in circulation, the most common one being the following. In a room of people, how many different handshakes are possible?
The answer is . To see this, enumerate the people present, and consider one person at a time. The first person may shake hands with other people. The next person may shake hands with other people, not counting the first person again. Continuing like this gives us a total number of
handshakes, which is exactly the answer given above.
Another popular handshake problem starts out similarly with people at a party. Not being able to shake hands with yourself, and not counting multiple handshakes with the same person, the problem is to show that there will always be two people at the party, who have shaken hands the same number of times.
The solution to this problem uses Dirichlet's box principle. If there exists a person at the party, who has shaken hands zero times, then every person at the party has shaken hands with at most other people. Since there are possible handshakes (from 0 to ), among people there must be two who have shaken hands the same amount of times. If there exists no person, who has shaken hands zero times, then all of the party guests have shaken hands at least once. This also amounts to possible handshakes (from 1 to ).