Q13 Matemática  (IMO Shortlist 2008)

Para $n\ge 2$, seja $S_1$, $S_2$, $\dots$, $S_{2^n}$ $2^n$ subconjuntos de $A=\{1,2,3,ldots,2^{n+1}\}$ que satisfazem a seguinte propriedade: Não existem índices $a$ e $b$ com $a<b$ e elementos $x$, $y$, $z\in A$ com $x<y<z$ e $y$, $z\in S_a$ e $x$, $z\in S_b$. Prove que pelo menos um dos conjuntos $S_1$, $S_2$, $\dots$, $S_{2^n}$ não contém mais do que $4n$ elementos. Proposto por Gerhard Woeginger, Holanda