Students have taken a test paper in each of () subjects. It is known that for any subject exactly three students get the best score in the subject, and for any two subjects exactly one student gets the best score in every one of these two subjects. Determine the smallest so that the above conditions imply that exactly one student gets the best score in every one of the subjects.
Solution
The smallest is .
We use terminologies in set theory. Let be sets corresponding to the subjects, while the elements correspond to the students getting the best score in that subject. It is given that and for any . Suppose . We shall show that .
WLOG assume is an element that belongs to the most number of sets. Suppose for and for . Suppose on the contrary that .
Consider . For , since , each consists of one of . Also, each of belongs to at most one of these 's, since the only common element in these sets is , but . Thus, . This means each element belongs to at most sets.
Now, suppose . Since each of belongs to at most two other sets, we must have , which is a contradiction. Therefore, .
It suffices to provide an example for such that is empty, since we can remove some sets if is less than . Indeed, consider
It is routine to check that for all , but no element belongs to all of them.