Maths Olympiad Prep

Library / /87 of 136

, 1997

Combinatorics Difficulty 8.1 Shortlist Prove it Hong Kong

Find the maximum number of sets which simultaneously satisfy the following 3 conditions:
(i) any of the sets consists of 4 elements;
(ii) any two different sets have exactly 2 common elements;
(iii) no two elements are common to all the sets.

Solution

The maximum number of sets is 77.
We first assume there are at least 88 sets. WLOG assume 11 and 22 are common elements of at least two sets.

* If there are 44 sets containing both 11 and 22, say {1,2,3,4}\{1, 2, 3, 4\}, {1,2,5,6}\{1, 2, 5, 6\}, {1,2,7,8}\{1, 2, 7, 8\}, {1,2,9,10}\{1, 2, 9, 10\}, then all other sets must contain both 11 and 22. Otherwise a set has to contain 1,3,5,7,91, 3, 5, 7, 9 (up to renaming of the elements) or 3,4,,103, 4, \ldots, 10, which contradicts condition (i). But now condition (iii) is violated. So this case is not possible.

* If exactly 33 sets contain both aa and bb, say {1,2,3,4}\{1, 2, 3, 4\}, {1,2,5,6}\{1, 2, 5, 6\}, {1,2,7,8}\{1, 2, 7, 8\}, then all other sets must contain one of 1,21, 2, one of 3,43, 4, one of 5,65, 6 and one of 7,87, 8. Consider the following triples of numbers:
{3,5,7},{4,6,8}, {3,5,8},{4,6,7}, {3,6,7},{4,5,8}, {3,6,8},{4,5,7}.\{3, 5, 7\}, \{4, 6, 8\}, \ \{3, 5, 8\}, \{4, 6, 7\}, \ \{3, 6, 7\}, \{4, 5, 8\}, \ \{3, 6, 8\}, \{4, 5, 7\}.

At most one triple in each row may be a subset of one of the sets, since otherwise the two sets containing the triples in the same row share at most one element. Therefore, the number of sets is at most 3+4=73+4 = 7, contradiction.

* If exactly 22 sets contain both aa and bb, say {1,2,3,4}\{1, 2, 3, 4\} and {1,2,5,6}\{1, 2, 5, 6\}, then except {3,4,5,6}\{3, 4, 5, 6\}, all other sets must contain one of 1,21, 2, one of 3,43, 4 and one of 5,65, 6. Consider the following triples of numbers:
{1,3,5},{2,4,6},{1,3,6},{2,4,5},{1,4,5},{2,3,6},{1,4,6},{2,3,5}. \begin{aligned} \{1, 3, 5\}, \{2, 4, 6\}, \\ \{1, 3, 6\}, \{2, 4, 5\}, \\ \{1, 4, 5\}, \{2, 3, 6\}, \\ \{1, 4, 6\}, \{2, 3, 5\}. \end{aligned}
Again, at most one triple in each row may be a subset of one of the sets. Therefore, the number of sets is at most 2+1+4=72+1+4 = 7, contradiction.

Finally, we can find 77 sets satisfying all the given conditions, for example,
{1,2,3,4},{1,2,5,6},{1,2,7,8},{1,3,5,7},{1,3,6,8},{1,4,5,8},{1,4,6,7}. \{1, 2, 3, 4\}, \{1, 2, 5, 6\}, \{1, 2, 7, 8\}, \{1, 3, 5, 7\}, \{1, 3, 6, 8\}, \{1, 4, 5, 8\}, \{1, 4, 6, 7\}.
Therefore, the answer is 77.

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.