Maths Olympiad Prep

Library / /68 of 299

Combinatorics Difficulty 6.0 AIME, harder Prove it Iran

Find the maximum number of 5-element subsets of the set {1,2,,20}\{1, 2, \dots, 20\} such that the intersection of any pair of these subsets has exactly one element.

Solution

The answer is 1616. For the example consider the following family of 55-element subsets.
{1,2,3,4,5}{2,6,10,14,18}{2,7,11,15,19}{2,8,12,16,20}{1,6,7,8,9}{3,8,13,15,18}{3,9,12,14,19}{3,6,11,17,20}{1,10,11,12,13}{4,7,12,17,18}{4,6,13,16,19}{4,9,10,15,20}{1,14,15,16,17}{5,9,11,16,18}{5,8,10,17,19}{5,7,13,14,20} \begin{aligned} \{1, 2, 3, 4, 5\} & & \{2, 6, 10, 14, 18\} \\ \{2, 7, 11, 15, 19\} & & \{2, 8, 12, 16, 20\} \\ \{1, 6, 7, 8, 9\} & & \{3, 8, 13, 15, 18\} \\ \{3, 9, 12, 14, 19\} & & \{3, 6, 11, 17, 20\} \\ \{1, 10, 11, 12, 13\} & & \{4, 7, 12, 17, 18\} \\ \{4, 6, 13, 16, 19\} & & \{4, 9, 10, 15, 20\} \\ \{1, 14, 15, 16, 17\} & & \{5, 9, 11, 16, 18\} \\ \{5, 8, 10, 17, 19\} & & \{5, 7, 13, 14, 20\} \end{aligned}
Next, we prove that there is no such family with 1717 subsets. Without loss of generality we can assume that A1={1,2,3,4,5}A_1 = \{1, 2, 3, 4, 5\} is among the subsets. By pigeonhole principle there are at least four subsets such that intersection of each of them with A1A_1 is the same. Without loss of generality call these four subsets A2,A3,A4A_2, A_3, A_4 and A5A_5, and assume that for all integer numbers 2i52 \le i \le 5, AiA1={1}A_i \cap A_1 = \{1\}. So by assumption we also know that AiAj={1}A_i \cap A_j = \{1\} for all integer numbers 2i<j52 \le i < j \le 5. Hence A1A2A3A4A5A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 has 2121 elements which is a contradiction. ■

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.