Library / /28 of 39

, 2012

Combinatorics Difficulty 6.4 National olympiad Prove it Belarus

Determine the greatest possible value of $n$ that satisfies the following condition: for any choice of $n$ subsets $M_1, ..., M_n$ of the set $M = \{1, 2, ..., n\}$ satisfying the conditions
i) $i \in M_i$ ; and
ii) $i \in M_j \Leftrightarrow j \notin M_i$ for all $i \neq j$ ,
there exist $M_k$ and $M_l$ such that $M_k \cup M_l = M$ .

Solution

(Solution of A. Zhuk.) First, if $M = \{1, 2, ..., 6\}$ , then due to the conditions i) and ii) we have $|M_1| + |M_2| + ... + |M_6| = 21$ . It follows that $|M_k| \ge 4$ for some index $k$ . There is nothing to prove if $|M_k| = 6$ . If $|M_k| = 5$ , then there exists $l \notin M_k$ , and $M_k \cup M_l = M$ . If $|M_k| = 4$ , then there exist distinct $l$ , $m \notin M_k$ , and either $M_k \cup M_l = M$ or $M_k \cup M_m = M$ .
It remains to show that $n = 7$ does not satisfy the problem condition. Indeed, for $M = \{1, 2, ..., 7\}$ , the sets $M_1 = \{1, 2, 3, 4\}$ , $M_2 = \{2, 4, 6, 7\}$ , $M_3 = \{2, 3, 5, 7\}$ , $M_4 = \{3, 4, 5, 6\}$ , $M_5 = \{1, 2, 5, 6\}$ , $M_6 = \{1, 3, 6, 7\}$ , $M_1 = \{1, 4, 5, 7\}$ give the counterexample needed.

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.