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 
).
