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.
First off, I assume the question means that there were AT LEAST 2 people at the party who had shaken hands the same number of times, not EXACTLY 2 people... it is easy to think of a situation where more than two people had shaken hands the same number of times, e.g. a party of three people where everybody knew everybody else.
Solution: At any given moment, there are n people at the party. Each person can know anywhere from 0 to (n-1) other people (since we assume that one cannot "know oneself", at least not shake one's own hand). Thus, for n different people there are n different numbers of handshakes one can possibly make (0, 1, 2, ... , n-1). However, it is impossible for there to be a person who knows (n-1) people AND a person who knows 0 people at a party; the first represents someone who knows everybody else, the second someone who knows nobody, and the two cannot coexist. Thus, there are only (n-1) possible different handshake counts a person at the party can have, and n people at the party; therefore, at least two people must have made the same number of handshakes (I think they called this pigeon-hole theory in college, but that could be wrong).
Solution
