Question

1/ Imagine a party with n people. When a person comes to the party they go and shake hands with a few other people (but not necessarily everyone - in fact there can be unfriendly people who do not shake hands with anyone!). None of the attendees narcissistic enough to shake hands with themselves. Prove that there are two people who shake the same number of hands.

For example, suppose 3 people attend the party and everyone shakes hand with everyone. Well, then all 3 shake 2 hands each. If, on the other hand one of them is unfriendly and does not shake hands with anyone but the other two are not, then there are 2 people who shake 1 hand each. Similarly, if all of them are unfriendly, there are 3 people each shaking 0 hands each. In all the cases, the claim is true. You have to prove this in general-not necessarily by case analysis.

Answer 1

Step 1:

Given:

Number of people in the party = n

Step2:
Consider a person A in the party.

Step 3:

The person A can shake hands with between 0 and n-1 people.

REASON: He cannot shake hands with himself.

Thus, the number of possibilities the peson A can shake hand is n.

Step 4:

Now: 0 and n-1 are mutually exclusive.

REASON: If person A shakes hands with everyone else, there is no one who has not shook hands with no one.

Thus, there are n-1 possibilies of people the person A can shake with.

Step 5:

Thus, there are n people in the party. There are n-1 possibilities each person can shake hands.

Thus, by Pigeon Hole Principle, there are two people who shake the same number of hands.