Maths Olympiad Prep

Library / /12 of 24

Combinatorics Difficulty 6.3 National olympiad Prove it Belarus

Determine the largest possible number of three-element sets that can be formed so that any two of these sets have exactly one common element, but there is not an element that belongs to all these sets.

Solution

Answer: 7 sets.
Let NN be the required number of 3-element sets satisfying the problem condition. Suppose that N8N \ge 8. Let M={x,y,z}M = \{x, y, z\} be one of these sets. Since the number of the remaining sets is greater than or equal to 7 and each such set has exactly one common element with MM, we see that there exists an element of MM (say, xx) that belongs to at least [7/3]=3[7/3] = 3 sets. Let the sets M1,M2,M3M_1, M_2, M_3 contain xx. By condition, there is not an element that belongs to all sets, so there exists a set (say, M0M_0) such that there is an element from MM (say, yy), which belongs to M0M_0. It follows that xM0x \notin M_0. Since any two of the sets M1,M2,M3M_1, M_2, M_3 and MM have not common elements except for xx (and xM0x \notin M_0), so all four elements of the intersection of M0M_0 with M1,M2,M3M_1, M_2, M_3, MM are distinct. Therefore M0M_0 consists of at least four elements, a contradiction. Thus, N7N \le 7.

It remains to show the example for N=7N = 7. The required sets (see the Fig.) are {A,K,B}\{A, K, B\}, {A,P,M}\{A, P, M\}, {A,N,C}\{A, N, C\}, {B,M,C}\{B, M, C\}, {B,P,N}\{B, P, N\}, {C,P,K}\{C, P, K\}, {K,M,N}\{K, M, N\}.

Figure 1

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 and solution reproduced as published; topic and difficulty added by this site.