Maths Olympiad Prep

Library / /69 of 108

Combinatorics Difficulty 6.3 National Olympiad Prove it Mongolia

Find all the positive integers nn such that there exist nn sets A1,A2,,AnA_1, A_2, \dots, A_n such that each of them has exactly 55 elements, any two of these nn sets have exactly one common element and the union of these sets consists of nn elements.

Solution

Let us assume that the union of the sets consists of integers from 11 to nn. Let SiS_i denote the number of sets that ii belongs to. Then the total number of elements of nn sets is 5n=S1+S2++Sn5n = S_1 + S_2 + \dots + S_n (\bullet).

Let us assume S1>5S_1 > 5 and 1A1,1A2,1A3,1A4,1A5,1A61 \in A_1, 1 \in A_2, 1 \in A_3, 1 \in A_4, 1 \in A_5, 1 \in A_6. If 1Ai,i=1,n1 \in A_i, i = 1, \overline{n}, then the remaining 4n4n elements have to be different. Because AiAj=1,ij|A_i \cap A_j| = 1, i \neq j holds. That means, we have 4n+14n+1 different elements. It contradicts to A1A2An=n|A_1 \cup A_2 \cup \dots \cup A_n| = n. Thus we can assume that 1A71 \notin A_7.

Since AiAj=1|A_i \cap A_j| = 1 for 1i,j61 \le i, j \le 6, the intersections of A7A_7 with A1,A2,,A6A_1, A_2, \dots, A_6 are all different. Hence A76|A_7| \ge 6. But it contradicts to A7=5|A_7| = 5. This leads to S15S_1 \le 5. Analogously, Sk5S_k \le 5 for k=1,nk = \overline{1, n}. Considering ()(*), Sk=5S_k = 5 holds for i=1,ni = \overline{1, n}. Hence the number of sets is n=45+1=21n = 4 \cdot 5 + 1 = 21. The construction is:

A1={1,2,3,4,5}A2={1,6,7,8,9}A3={1,10,11,12,13}A4={1,14,15,16,17}A5={1,18,19,20,21}A6={2,6,10,14,18}A7={2,7,11,15,19}A8={2,8,12,16,20}A9={2,9,13,17,21}A10={3,6,7,8,9}A11={3,10,11,12,13}A12={3,14,15,16,17}A13={3,18,19,20,21}A14={4,6,10,14,18}A15={4,7,11,15,19}A16={4,8,12,16,20}A17={4,9,13,17,21}A18={5,6,7,8,9}A19={5,10,11,12,13}A20={5,14,15,16,17}A21={5,18,19,20,21}. \begin{align*} A_1 &= \{1, 2, 3, 4, 5\} & A_2 &= \{1, 6, 7, 8, 9\} & A_3 &= \{1, 10, 11, 12, 13\} \\ A_4 &= \{1, 14, 15, 16, 17\} & A_5 &= \{1, 18, 19, 20, 21\} & A_6 &= \{2, 6, 10, 14, 18\} \\ A_7 &= \{2, 7, 11, 15, 19\} & A_8 &= \{2, 8, 12, 16, 20\} & A_9 &= \{2, 9, 13, 17, 21\} \\ A_{10} &= \{3, 6, 7, 8, 9\} & A_{11} &= \{3, 10, 11, 12, 13\} & A_{12} &= \{3, 14, 15, 16, 17\} \\ A_{13} &= \{3, 18, 19, 20, 21\} & A_{14} &= \{4, 6, 10, 14, 18\} & A_{15} &= \{4, 7, 11, 15, 19\} \\ A_{16} &= \{4, 8, 12, 16, 20\} & A_{17} &= \{4, 9, 13, 17, 21\} & A_{18} &= \{5, 6, 7, 8, 9\} \\ A_{19} &= \{5, 10, 11, 12, 13\} & A_{20} &= \{5, 14, 15, 16, 17\} & A_{21} &= \{5, 18, 19, 20, 21\}. \end{align*}

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.