Maths Olympiad Prep

Library / /37 of 73

Combinatorics Difficulty 8.1 Shortlist Prove it Turkey

For a given integer n3n \ge 3, let S1,S2,,SmS_1, S_2, \dots, S_m be distinct three-element subsets of the set {1,2,,n}\{1, 2, \dots, n\} such that for each 1i,jm;ij1 \le i, j \le m; i \ne j the sets SiSjS_i \cap S_j contain exactly one element. Determine the maximal possible value of mm for each nn.

Solution

For each nn let f(n)f(n) be the maximal value of mm. Readily f(3)=f(4)=1f(3) = f(4) = 1 and f(5)=2f(5) = 2. If n=6n = 6 each number belongs to at most 2 subsets. Thus, f(6)623=4f(6) \le \frac{6 \cdot 2}{3} = 4. Therefore f(6)=4f(6) = 4 since the example {1,2,3},{1,4,5},{2,4,6},{3,5,6}\{1, 2, 3\}, \{1, 4, 5\}, \{2, 4, 6\}, \{3, 5, 6\} works.

Let n7n \ge 7. If some element belongs to all subsets then readily f(n)n12f(n) \le \lfloor \frac{n-1}{2} \rfloor. The example {1,2,3},{1,4,5},{1,6,7},,{1,n1,n}\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \dots, \{1, n-1, n\} for odd nn shows that in this case f(n)=n12f(n) = \lfloor \frac{n-1}{2} \rfloor.

Suppose that no element belongs to all subsets. If some number aa belongs to at least 4 subsets, say S1,S2,S3,S4S_1, S_2, S_3, S_4 and some S5S_5 does not contain aa then S5S_5 should contain at least 4 elements since it contains at least one element from each Si{a}S_i - \{a\} for i=1,2,3,4i = 1, 2, 3, 4, contradiction.

Suppose that each aa belongs to at most 3 subsets. Let us fix one of the subsets: {a1,a2,a3}\{a_1, a_2, a_3\}. Then there are at most 2 subsets containing each aia_i, i=1,2,3i = 1, 2, 3 and there are at most 1+32=71+3 \cdot 2 = 7 subsets. The example for 7 subsets: {1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}\{1, 2, 4\}, \{2, 3, 5\}, \{3, 4, 6\}, \{4, 5, 7\}, \{5, 6, 1\}, \{6, 7, 2\}, \{7, 1, 3\}.

Thus, f(n)=max{7,n12}f(n) = \max\{7, \lfloor \frac{n-1}{2} \rfloor\}.

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.