concurrent

Opgave - BaMO 1997 vraag 2

Zij $A=\{A_1,A_2,\ldots,A_k\}\ (k>1)$ een verzameling van deelverzamelingen van een verzameling $S$ met $|S|=n$, zodat voor alle $x,y\in S$, er een $A_i\in A$ is zodat $x\in A_1$ en $y\in A\backslash A_i$ of $x\in A\backslash A_i$ en $y\in A_i$. Toon aan dat $k\geq\log_2n$.