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.
 A: You have a set $A$ with $n$ elements. 
Then there is a collection of $k$ sets $\{A_1,\ldots,A_k\}$, each of which is a subset of $A$, that is, $A_i \subseteq A$ for $1 \leq i \leq k$. You need to prove that

If for any pair $x,y \in A$ there is a set $A_i$ that distinguishes between $x$ and $y$ (that is, contains exactly one of them), then there are many sets $A_i$, namely $2^k \geq n$.

For example for $A = \{1,2,3,4,5\}$ and $A_1 = \{1,2\}, A_2 = \{2,3,4\}$ we have that $A_1$ distinguishes between $2$ and $3$, but not between $3$ and $4$. In fact no set distinguishes between $3$ and $4$.
Another instance might be $A = \{1,2,3,4\}$ and $A_1 = \{1,2\}$ and $A_2 = \{1,3\}$. In this setting every pair of elements $x,y \in A$ is distinguishable by sets $A_1,A_2$, and indeed $2^2 \geq 4$.
Hint:

 Consider function $f : A \to \mathbb{N}$ given by \begin{align} f(a) = 1\cdot\chi_{A_1}(a) + 2\cdot\chi_{A_2}(a) + 4\cdot\chi_{A_3} + \ldots + 2^{k-1}\cdot\chi_{A_k}(a), \end{align}
 where $\chi_{A_i}(x)$ is the characteristic function of $A_i$, i.e.
 \begin{align} \chi_{A_i}(x) = \begin{cases} 1 &\text{ if }x \in A_i,\\0&\text{ otherwise.}\end{cases}\end{align}
 Observe that for any element $a \in A$ we have $0 \leq f(a) \leq 2^k-1$.

Solution:

 In other words, if $n > 2^k$ then there are two elements $x$ and $y$ such that $f(x) = f(y)$. This in turn implies that $\chi_{A_i}(x) = \chi_{A_j}(y)$ for any $1 \leq i,j \leq k$, so no $A_i$ distinguishes these two elements.

I hope this helps $\ddot\smile$
A: Here's a rephrasing: let $S=\{A_1,\ldots,A_k\}$ be a collection of subsets of an $n$-element set $A.$   Let $x,$ $y$ be a pair of elements of $A.$  We will say that $S$ has the XOR property for $(x,y)$ if at least one element of $S$ contains only one of $x,$ $y.$  In other words, $S$ would fail to have the XOR property for $x,$ $y$ if every element of $S$ contained either both $x$ and $y$ or neither $x$ nor $y.$
The question asks you to prove that if $S$ has the XOR property for all pairs of elements of $A,$ then $S$ can't be too small.  In particular, $S$ must consist of at least $\log_2 n$ subsets of $A.$
A: 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$.
