TITLE: Number of subsets required to satisfy condition
QUESTION [0 upvotes]: Suppose $S$ is a set with $n > 1$ elements and $A_1 ,...,A_m$ are subsets of $S$ with
the following property:  if $x$, $y$ $\in$ $S$ and $x$ $\neq$ $y$, then there exists $i$ $\in$ $ \{1,...,m\} $ such that,
either $x$ $\in$ $A_i$ and $y$ $\notin$ $A_i$ , or $y$ $\in$ $A_i$ and $x$ $\notin$ $A_i$ . Then the following necessarily holds:
A) $n$ $=$ $2^m$
B) $n$ $\leq$ $2^m$
C) $n\gt2^m$
Here's what I tried:
There are a total of $2^n$ subsets of $S$. 
$2^{(n-2)}$ is therefore the number of sets which contain neither $x$ nor $y$, including the null set.
$2^{(n-2)}$ must also be the number of sets which contain both $x$ and $y$.
Thus the maximum number of subsets which do not satisfy our property is: 
$2^{(n-2)}$ $+$ $2^{(n-2)}$ $=$ $2^{(n-1)}$
So $m$ must be $\geq$  $2^{(n-1)} + 1$
I think the answer should then be B) $n \leq 2^{(m)}$
Are my reasoning and method correct? Is there a better method of solving this question?

REPLY [0 votes]: I get (b) too, by this reasoning:
The condition can be rephrased as: There are not two different $x,y\in S$ that are in exactly the same $A_i$s.
Or, in yet other words, the function
$$ f: S\to \mathcal P(\{1,2,\ldots,m\}) : x \mapsto \{ i\mid x\in A_i \} $$
is injective. This tells us that $|S|\le 2^m$.
The only question is now whether (b) can be strengthened to (a), but that is not the case because we can easily find an example with, for example, $n=m=2$:
$$ S=\{1,2\} \qquad\qquad A_1=\{1\} \qquad A_2 = \{2\} $$
However, this example doesn't satisfy your claim $m\ge 2^{n-1}+1$, so your reasoning can't be right.
{"set_name": "stack_exchange", "score": 0, "question_id": 2129702}