Prove that at a party where some people shake hands, the number of people who shake hands with an odd number of people is an even number.

If there are n people, each person could shake hands with 0 people, 1 person, 2 people,... on up to shaking hands with n − 1
people. Count how many different answers there are to asking the person the question "How many hands did you shake?" How many people are there? If the people are the pigeons, and the possible answers to the question "how many hands did you shake" are the holes, can we conclude anything yet? No? How about now noticing that at least one of the holes "I shook hands with noone" or "I shook hands with everyone" has to be empty... now what?

"Since there are more pigeons than holes there must be a hole with at least two pigeons in the same hole" Now, replace the word "pigeons" and "holes" with the appropriate terms for the context of your specific question, remember we are talking about people and number of handshakes they participated in.