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?

Question

Paco

Mathematics

18 July, 14:02

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?

+2

Answers (1)

Know the Answer?

Rudy Shaw · Answer 1

Step-by-step 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.