Olympiad Maths Prep

Library / /4 of 4

Combinatorics Difficulty 4.2 AIME Prove it Turkey

In an exam every question is solved by exactly four students, every pair of questions is solved by exactly one student, and none of the students solved all of the questions. Find the maximum possible number of questions in this exam.

Solution

Suppose S1S_1 solved Q1,,QkQ_1, \dots, Q_k, but not Qk+1Q_{k+1} where k>4k > 4. Since Qk+1Q_{k+1} is solved by exactly 4 students, and QiQ_i and Qk+1Q_{k+1} are solved by exactly one student for each 1ik1 \le i \le k, there must be another student who solved two of the questions Q1,,QkQ_1, \dots, Q_k besides S1S_1, a contradiction. Therefore k4k \le 4. Since Q1Q_1 is solved by exactly four students, the number of questions cannot be more than 1+43=131+4 \cdot 3 = 13.

On the other hand, an exam with 13 questions where
Q1Q_1 is solved by S1,S2,S3,S4S_1, S_2, S_3, S_4; Q2Q_2 is solved by S1,S5,S6,S7S_1, S_5, S_6, S_7; Q3Q_3 is solved by S1,S8,S9,S10S_1, S_8, S_9, S_{10}; Q4Q_4 is solved by S1,S11,S12,S13S_1, S_{11}, S_{12}, S_{13}; Q5Q_5 is solved by S2,S5,S9,S13S_2, S_5, S_9, S_{13}; Q6Q_6 is solved by S2,S6,S10,S11S_2, S_6, S_{10}, S_{11}; Q7Q_7 is solved by S2,S7,S8,S12S_2, S_7, S_8, S_{12}; Q8Q_8 is solved by S3,S5,S10,S12S_3, S_5, S_{10}, S_{12}; Q9Q_9 is solved by S3,S6,S8,S13S_3, S_6, S_8, S_{13}; Q10Q_{10} is solved by S3,S7,S9,S11S_3, S_7, S_9, S_{11}; Q11Q_{11} is solved by S4,S5,S8,S11S_4, S_5, S_8, S_{11}; Q12Q_{12} is solved by S4,S6,S9,S12S_4, S_6, S_9, S_{12}; Q13Q_{13} is solved by S4,S7,S10,S13S_4, S_7, S_{10}, S_{13}
satisfies the conditions of the question.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.