Question

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) 202

The question was posed to me during an internship interview.

The origin of the question is Counting topic in section Counting of Discrete Mathematics

Answer 1

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.