Skip to main content
OlympiadHQ

Browse · MathNet

Print

Final Round

Belarus counting and probability

Problem

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.

problem
Solution
Answer: 7 sets. Let be the required number of 3-element sets satisfying the problem condition. Suppose that . Let 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 , we see that there exists an element of (say, ) that belongs to at least sets. Let the sets contain . By condition, there is not an element that belongs to all sets, so there exists a set (say, ) such that there is an element from (say, ), which belongs to . It follows that . Since any two of the sets and have not common elements except for (and ), so all four elements of the intersection of with , are distinct. Therefore consists of at least four elements, a contradiction. Thus, .

It remains to show the example for . The required sets (see the Fig.) are , , , , , , .

Final answer
7

Techniques

Pigeonhole principleColoring schemes, extremal arguments