Let be an integer, . Each student in a school is practising hobbies the most. Among any students there exist two students who have a common hobby. Find the smallest number of students for which there must exist a hobby which is practised by at least 3 students.
Solution
If the number of students is , let us split the students to groups, each with students. Assume that each student has a unique common hobby with every other student in the same group and none of the students is practising any other hobby. Then each student has exactly hobbies but among each students at least two of them belong to the same group, i.e., have a common hobby. Hence the conditions of the problem are satisfied but there exists no hobby which is practised by more than 2 students. If there are less than students at the school, similar construction can be used with a suitable number of students omitted.
Let us show that if there are at least students at school, then there must exist a hobby that is practised by at least 3 students. Assume the contrary that every hobby is practised by 2 students at most. Let us form a group of students in which each pair of students have no hobby in common by adding in each iteration to initially empty group one student who does not have a common hobby with any of the students already assigned to the group. As every student has hobbies the most and each hobby can be common with only one other student, after iterations there are at most students who cannot be added to the group in the subsequent iterations. As , it is still possible to add another student to a group of students. Therefore, there exists a group of students, in which there exists no pair who have a common hobby. That contradicts the conditions of the problem statement.