Maths Olympiad Prep

Library / /82 of 94

Combinatorics Difficulty 6.8 National Olympiad Prove it Hong Kong

Students have taken a test paper in each of nn (n3n \ge 3) subjects. It is known that for any subject exactly three students get the best score in the subject, and for any two subjects exactly one student gets the best score in every one of these two subjects. Determine the smallest nn so that the above conditions imply that exactly one student gets the best score in every one of the nn subjects.

Solution

The smallest nn is 88.
We use terminologies in set theory. Let A1,A2,,AnA_1, A_2, \dots, A_n be sets corresponding to the nn subjects, while the elements correspond to the students getting the best score in that subject. It is given that Aj=3|A_j| = 3 and AiAj=1|A_i \cap A_j| = 1 for any 1i<jn1 \le i < j \le n. Suppose n8n \ge 8. We shall show that A1A2An1|A_1 \cap A_2 \cap \dots \cap A_n| \ge 1.
WLOG assume 11 is an element that belongs to the most number of sets. Suppose 1Aj1 \in A_j for j=1,2,,mj = 1, 2, \dots, m and 1Aj1 \notin A_j for j=m+1,m+2,,nj = m+1, m+2, \dots, n. Suppose on the contrary that m<nm < n.
Consider An={a,b,c}A_n = \{a, b, c\}. For j=1,2,,mj = 1, 2, \dots, m, since AnAj=1|A_n \cap A_j| = 1, each AjA_j consists of one of a,b,ca, b, c. Also, each of a,b,ca, b, c belongs to at most one of these AjA_j's, since the only common element in these sets is 11, but 1An1 \notin A_n. Thus, m3m \le 3. This means each element belongs to at most 33 sets.
Now, suppose A1={1,2,3}A_1 = \{1, 2, 3\}. Since each of 1,2,31, 2, 3 belongs to at most two other sets, we must have n1+2×3=7n \le 1 + 2 \times 3 = 7, which is a contradiction. Therefore, A1A2An1|A_1 \cap A_2 \cap \dots \cap A_n| \ge 1.
It suffices to provide an example for n=7n = 7 such that A1A2AnA_1 \cap A_2 \cap \dots \cap A_n is empty, since we can remove some sets if nn is less than 77. Indeed, consider
A1={1,2,3}, A2={1,4,5}, A3={1,6,7}, A4={2,4,6}, A5={2,5,7}, A6={3,4,7}, A7={3,5,6}. A_1 = \{1, 2, 3\},\ A_2 = \{1, 4, 5\},\ A_3 = \{1, 6, 7\},\ A_4 = \{2, 4, 6\},\ A_5 = \{2, 5, 7\},\ A_6 = \{3, 4, 7\},\ A_7 = \{3, 5, 6\}.
It is routine to check that AiAj=1|A_i \cap A_j| = 1 for all i,ji, j, but no element belongs to all of them.

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.