Problem:
Let and be integers. Prove that in a group of people such that there are two familiar people among any , there is a person who is familiar with people. Does the statement remain true if ?
Problem:
Let and be integers. Prove that in a group of people such that there are two familiar people among any , there is a person who is familiar with people. Does the statement remain true if ?
Solution:
Consider a group with maximal number of people such that any two of them are not familiar. It is clear that if there are people in this group, then . Moreover, the maximality of implies that any of the other people is familiar to at least one of the people in the group. Hence some of these people is familiar to at least people. Since
there is a person who is familiar to people.
Let and consider groups by people such that any two people from one group are familiar and there are no familiar people from different groups. Then among any people there are two from one and the same group, i.e. they are familiar. On the other hand, any of the people is familiar to of the other and hence the statement is not true if .