1.

In a group of 267 people how many friends are there who have an identical number of friends in that group?(a) 266(b) 2(c) 138(d) 202The question was posed to me during an internship interview.The origin of the question is Counting topic in section Counting of Discrete Mathematics

Answer»

Correct choice is (b) 2

The best explanation: Suppose each of the 267 members of the group has at least 1 friend. In this case, each of the 267 members of the group will have 1 to 267-1=266 friends. Now, consider the numbers from 1 to n-1 as holes and the n members as pigeons. Since there is n-1 holes and n pigeons there MUST exist a hole which must CONTAIN more than one pigeon. That means there must exist a number from 1 to n-1 which would contain more than 1 member. So, in a group of n members there must exist at least TWO persons having equal number of friends. A similar case occurs when there exist a PERSON having no friends.



Discussion

No Comment Found

Related InterviewSolutions