Question

4.   
Show that if n
people attend a party and some shake hands with others (but not with
themselves), then at the end, there are at least two people who have shaken
hands with the same number of people.

Answer 1

Principle : Pigeon Hole principle


Explanation :
A person can shake hands with between 0 and N-1 people since you cannot shake hands with your self. That is N possibilities. If one person has shaken hands with everyone else, then there is no one who hasn’t shook hands with no one ( means all have shook hands with at least 1 ) . And the other way around. So 0 and N-1 possibilities are mutual exclusive. So we are down to N-1 possibilities of people each person can shake hands with.

So if there are N people and N-1 possibilities to the number of people each person can shake hands with then  by Pigeon Hole principle at least 2 people have shook hands with an equal amount of people