Maths Olympiad Prep

Library / /43 of 48

Combinatorics Difficulty 6.7 National Olympiad Prove it Hong Kong

In a school there are 20082008 students. Students are members of certain committees. A committee has at most 10041004 members and every two students join a common committee.

a. Determine the smallest possible number of committees in the school.

b. If it is further required that the union of any two committees consists of at most 18001800 students, will your answer in (a) still hold?

Solution

a. The smallest number of committees in the school is 66.
If a student joins at most 22 committees, that student shares a common committee with at most 2(10041)=2008<20072(1004 - 1) = 2008 < 2007 students, which contradicts the assumption. Therefore, each student joins at least 33 committees. Thus, there are at least
3×20081004=6 \frac{3 \times 2008}{1004} = 6
committees.
The minimum value can be attained. For example, partition all students into 88 groups A,B,,HA, B, \dots, H, each consisting of 251251 students. We form the following 66 committees:
{A,B,C,D},{A,E,F,G},{A,B,E,H},{B,F,G,H},{C,D,G,H},{C,D,E,F}. \{A, B, C, D\}, \{A, E, F, G\}, \{A, B, E, H\}, \{B, F, G, H\}, \{C, D, G, H\}, \{C, D, E, F\}.
Each committee contains 251×4=1004251 \times 4 = 1004 students. One can check that every pair of groups belongs to at least one common committee, and so every pair of students joins a common committee.

b. Yes. One can check that every pair of committees in the example provided in part (a) consists of at most 77 groups only, and so the union consists of at most
251×7=1757<1800 251 \times 7 = 1757 < 1800
students.

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.