As the people arrived at the party, they had to greet everyone they knew in the hall with a handshake.

Show that at every moment, there were 2 people at the party who had shaken hands the same number of times.

For n guests, the minimum number of people that one can shake hands with is zero, while the maximum number is n-1 (you aren’t shaking hands with yourself, after all). However, these two conditions are mutually exclusive, because if one person has shaken the hands of all of the n-1 other guests, another person cannot have shaken nobody’s hand, and vice versa. Therefore, for n guests, there are only n-1 possible number of handshakes, so at least two partiers must have the same number of handshakes.

Posted by Bryan on 2003-05-22 04:43:20