Maths Olympiad Prep

Library / /24 of 48

Combinatorics Difficulty 5.6 AIME, harder Prove it Hong Kong

In a school there are 12001200 students. Each student must join exactly kk clubs. Given that there is a common club joined by every 2323 students, but there is no common club joined by all 12001200 students, find the smallest possible value of kk.

Solution

The answer is k=23k = 23.

We first show k23k \le 23. We list the students as S1,S2,,S1200S_1, S_2, \dots, S_{1200} and the clubs as C1,C2,,C24C_1, C_2, \dots, C_{24}. Consider the following construction. For 1j241 \le j \le 24, student SjS_j joins clubs C1,,Cj1,Cj+1,,C24C_1, \dots, C_{j-1}, C_{j+1}, \dots, C_{24}. For 25j120025 \le j \le 1200, student SjS_j joins the same clubs as S1S_1. Then we can see every 2323 students have a common club, but all 12001200 students do not have a common club.

Now we show k23k \ge 23. Suppose a student SS joins clubs C1,C2,,CkC_1, C_2, \dots, C_k. Because all 12001200 students do not join a common club, for each 1jk1 \le j \le k, there is a student SjS_j not joining the club CjC_j. Hence the students S,S1,S2,,SkS, S_1, S_2, \dots, S_k do not have a common club, forcing k23k \ge 23. The proof is complete.

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.