Prove that if n people attend a party, there will be at least two people who shake the same number of hands.
combinatorics/same.handshakes New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Prove that if n people attend a party, there will be at least two people who shake the same number of hands. (Two people each shake one hand, five people shake no hands, etc.) [ Editor: as quoted in a June 1995 rec.puzzles thread "Hand-shaking"; the original poser is not identified in the collected posting. ]
Show solution
This is false. Counterexample: n=3. Persons A and B shake hands, then persons A and C shake hands twice. Person A has shaken three hands, person B has shaken one, and person C has shaken two. If any given pair is only allowed to shake hands once, there's a simple proof by the Pigeonhole Principle. There are n partygoers and only n-1 possible values for the number of handshakes each person can make. (Each partygoer can only shake the hands of at most n-1 other people, and the values 0 and n-1 are mutually exclusive.) -- Jonathan S. Haas <positron@devel.trimarkint.com> (June 1995)