Maths Olympiad Prep

Library / /87 of 158

Combinatorics Difficulty 5.8 AIME, harder Prove it Estonia

Let mm be an integer, m2m \ge 2. Each student in a school is practising mm hobbies the most. Among any mm 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 m21=(m1)(m+1)m^2 - 1 = (m-1)(m+1), let us split the students to m1m-1 groups, each with m+1m+1 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 mm hobbies but among each mm 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 m21m^2 - 1 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 m2m^2 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 mm hobbies the most and each hobby can be common with only one other student, after ii iterations there are at most i(m+1)i(m + 1) students who cannot be added to the group in the subsequent iterations. As (m1)(m+1)<m2(m - 1)(m + 1) < m^2, it is still possible to add another student to a group of m1m - 1 students. Therefore, there exists a group of mm students, in which there exists no pair who have a common hobby. That contradicts the conditions of the problem statement.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.