There are people in a city. For some period of time every day a group of at least people went to a restaurant to have dinner. No group of people went together to more than one dinner. Prove that there exists a group of people such that at every dinner there was a person not belonging to this group.
, 2011
Solution
We can assume that at every dinner there were exactly people (just remove the surplus people from every dinner, which does not affect the condition that no group of people went together to two different dinners, and can only make the task of finding a suitable -people group harder).
Consider a group with the greatest possible cardinality such that at every dinner there was a person not from . Assume there are people in . It is sufficient to show that .
By the definition of , for every person there exists a group of people which went to the restaurant together one day. But , so there are exactly elements in . In other words, every consists of people from and the person . Also, for different people we obtain distinct intersections — otherwise the groups would have people in common, which by our assumptions would mean that , but this is not possible, since and .
Thus the number of people not in (equal to ) does not exceed the number of -element subsets of :
The right hand side is increasing for and is equal to for . Therefore , as desired.