19th 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 $\varnothing$ nor $E$ is in $M$. If none of $\{i\}$ and $\{i{\}}^{\prime }$ 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{\}}^{\prime }$ can not be in $M$ and hence exactly one of $\{i\}$ and $\{i{\}}^{\prime }$ belongs to $M$ for all $1\le i\le n$.

Observe that if $X\in M$, then we can replace it by $X^{\prime }$. 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=\varnothing$, then $1,2\notin B$.

If $A\cap B^{\prime }=\varnothing$, then $A\subset B$ and hence $1,2\in B$.

If $A^{\prime }\cap B=\varnothing$, then $B\subset A$ and hence $|B|=1$ by the choice of $A$. Thus, $1,2\notin B$.

If $A^{\prime }\cap B^{\prime }=\varnothing$, 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^{\prime }$ and $A\cap B=\varnothing$.

Therefore we conclude that $\{1,2\}\subset B$ or $\{1,2\}\cap B=\varnothing$ 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$.