Maths Olympiad Prep

Track / Stage 6 / 164 of 400 #1644 of 2444

Problem 1644

National Olympiad, first round
Combinatorics Difficulty 6.3 Prove it Belarus — Final Round · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.