Repeated handshake counts at a 26-person party
Question
There are people at a party, one of whom is a late arrival who shakes hands with each of the other . Other handshakes happen arbitrarily, with no one shaking the same person's hand twice. Must there be two people who shook exactly the same number of hands?
Short answer
Yes. Everyone has shaken at least one hand (the late arrival's) and at most , so the counts lie in . There are only possible values for people, so by pigeonhole two counts coincide.
Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 2.6 The Pigeon Hole Principle, 'Handshakes', p.20; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solution