TOPICS
Search

Handshake Problem


Various handshaking problems are in circulation, the most common one being the following. In a room of n people, how many different handshakes are possible?

The answer is (n; 2)=n(n-1)/2. To see this, enumerate the people present, and consider one person at a time. The first person may shake hands with n-1 other people. The next person may shake hands with n-2 other people, not counting the first person again. Continuing like this gives us a total number of

 (n-1)+(n-2)+...+2+1

handshakes, which is exactly the answer given above.

Another popular handshake problem starts out similarly with n>1 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 n-2 other people. Since there are n-1 possible handshakes (from 0 to n-2), among n 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 n-1 possible handshakes (from 1 to n-1).


See also

Cocktail Party Graph, Glove Problem, Party Problem

This entry contributed by Rasmus Hedegaard

Explore with Wolfram|Alpha

References

D'Angelo, J. P. and West, D. B. Mathematical Thinking: Problem-Solving and Proofs, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2000.

Cite this as:

Hedegaard, Rasmus. "Handshake Problem." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/HandshakeProblem.html

Subject classifications