Balkan MO problem Let $S = \{A_1,A_2,\ldots ,A_k\}$ be a collection of subsets of an $n$-element set $A$. If for any two elements $x, y \in A$ there is a subset $A_i \in S$ containing exactly one of the two elements $x, y$, prove that $2^k\geq n$.  
This is a question from Balkan MO 1997, and I did not quite understand the question, so I could not make any attempt. Please help.

Well here another formulation of the solution. Look at the Boolian algebra generated by $A_i$. This algebra has at most $2^k$ atoms. Now remark that the atoms are exactly the singleton subsets of $A$.
