Question

Show that in any group of 101 people there are at least two persons having the same number friends (It is assumed that if a person x is a friend of y then y is also a friend of x and we are only considering the friends amongst the group of people). How would you modify your proof if the number of people were not 101?

Answer 1

Explanation:

Let us assume that if possible in the group of 101, each had a different number of friends. Then the no of friends 101 persons have 0,1,2,....100 only since number of friends are integers and non negative.

Say P has 100 friends then P has all other persons as friends. In this case, there cannot be any one who has 0 friend. So a contradiction. Hence proved

Part ii: EVen if instead of 101, say n people are there same proof follows as

if different number of friends then they would be 0,1,2...n-1

If one person has n-1 friends then there cannot be any one who does not have any friend.

Thus same proof follows.