29° Olimpiada Matemática del Cono Sur

We will first show how to construct $n-2$ subsets of $\{1,2,\dots ,n\}$ satisfying the required conditions. Such subsets will be called nice. For $n=4$, we can take $A_1=\{1\}$ and $A_2=\{2,3\}$. For $n=5$, we can take $A_1=\{1\}$, $A_2=\{2,3\}$ and $A_3=\{2,4,5\}$. We show now that if there exist $n-2$ nice subsets for $n$, then there exist $n$ nice subsets for $n+2$. Let $A_1,A_2,\dots ,A_{n-2}$ be nice subsets for $n$. Consider: $$\bullet B_1=\{n+2\},$$ $$\bullet B_{i+1}=A_i\cup \{n+1\},\text{ for every }1\le i\le n-2,$$ $$\bullet B_n=\{1,2,\dots ,n\}.$$ It is easy to check that $B_1,B_2,\dots ,B_n$ are nice subsets for $n+2$. Now, it remains to be seen that it is not possible to construct $n-1$ nice subsets for $n$. Assume, by contradiction, that $A_1,\dots ,A_{n-1}$ are nice subsets for $n$. If $A_1=\{x\}$, then $A_{n-1}=\{1,\dots ,n\}\setminus \{x\}$. Since $A_2$ has two elements that are different from $x$, it follows that they are elements of $A_{n-1}$ and so, $A_2\subset A_{n-1}$, which is a contradiction.