Turkish Mathematical Olympiad

The answer is $2n-3$ and an example is $\{1\}, \{2\}, \dots, \{n\}, \{1,2\}, \{1,2,3\}, \dots, \{1,2,3,\dots, n-2\}$.

We will prove it by induction on $n$. For $n=2$, it is clear that $k$ is at most $1$. For $n=3$, it is easy to check that $k \le 3$. Let us assume that the answer is $2n-5$ for $n-1 \ge 3$. Let $M = \{A_1, A_2, \dots, A_k\}$ be a maximal collection satisfying the conditions for $n$. By the example above, $k \ge 2n-3$. Note that neither $\emptyset$ nor $E$ is in $M$. If none of $\{i\}$ and $\{i\}'$ is in $M$ for some $1 \le i \le n$, then we could add one of them and enlarge the collection. Clearly both $\{i\}$ and $\{i\}'$ can not be in $M$ and hence exactly one of $\{i\}$ and $\{i\}'$ belongs to $M$ for all $1 \le i \le n$.

Observe that if $X \in M$, then we can replace it by $X'$. Therefore we may assume that $|A_i| \le \frac{n}{2}$ for all $1 \le i \le n$.

Now let us choose a set $A \in M$ such that $|A| \ge 2$ and $|A| \le |B|$ for all $B \in M$ with $|B| \ge 2$. Since $2n-3 > n$, there exists at least one such set. Without loss of generality we may assume that $1, 2 \in A$. Then consider any set $B$ in $M$ other than $\{1\}, \{2\}$ and $A$.

If $A \cap B = \emptyset$, then $1, 2 \notin B$.

If $A \cap B' = \emptyset$, then $A \subset B$ and hence $1, 2 \in B$.

If $A' \cap B = \emptyset$, then $B \subset A$ and hence $|B| = 1$ by the choice of $A$. Thus, $1, 2 \notin B$.

If $A' \cap B' = \emptyset$, then $A \cup B = E$. But when $n$ is odd $|A|, |B| \le \frac{n-1}{2}$ and hence $|A \cup B| \le n-1$. And when $n$ is even, the only possible case is $|A| = |B| = \frac{n}{2}$, but then $B = A'$ and $A \cap B = \emptyset$.

Therefore we conclude that $\{1,2\} \subset B$ or $\{1,2\} \cap B = \emptyset$ for all $B$ in $M$ other than $\{1\}$ and $\{2\}$. Hence by removing $\{1\}$ and $\{2\}$ from $M$ and merging $1$ and $2$, we obtain a new maximal collection for $n-1$. By the induction hypothesis $k-2 \le 2n-5$ and we also know that $k \ge 2n-3$. Therefore $k = 2n-3$.