The question more formally can be written as follows,
Suppose there is a set $X$ with $|X|=n$. Suppose $S\subseteq \mathcal{P}(X)$ s.t. for any two-element subset $Y\subseteq X$ there is a $Z\in S$ with $|Z\cap Y|=1$. What can be the least cardinality of $S$? Should it be an increasing function based on $n$?
This is the reduction of a problem that I faced; I do not know much combinatorics to tackle this type of problem. I would be very grateful for any help/resources. Thank you in advance.
There should be $r=\lceil \log_2 n \rceil$ such sets.
Indeed, let us write the collection $S$ of sets as $S =$ $\{Z_1,Z_2,\ldots, Z_r\}$, so $r=|S|$. Then for each $x \in X$, let $f_i(x)$ be the binary variable that
is $1$ iff $x$ is in $Z_i$
and $0$ otherwise,
and let $f(x)$ be the $r$-bit string, where the $i$-th bit of $f(x)$ is $f_i(x)$. Or put another way, for each $x \in X$, let $f(x)$ be the $r$-bit string where the $i$-th bit of $f(x)$ is $1$ iff $x$ is in $Z_i$, and $0$ otherwise. Then for each two-element set $\{x,x'\}$ of $X$, there is a $Z_i \in S$ such that $|Z_i \cap \{x,x'\}|$ is $1$, iff there is a $Z_i \in S$ such that exactly one of $x,x'$ is in $Z_i$, or equivalently, there is an integer $i \in \{1,2,\ldots, r\}$ such that $f_i(x) \not = f_i(x')$, or also equivalently, iff $f(x)$ and $f(x')$ are distinct.
That means that there has to be at least $n$ such distinct $r$-bit strings of the form $f(x); x \in X$. However, the number of $r$-bit strings is at most $2^r$. So the number $r$ of sets in $S=\{Z_1,\ldots, Z_r\}$ has to satisfy $2^r \ge n$ or $r = \lceil \log_2 n \rceil$.
And this bound is achievable; simply assign each element $x$ of $X$ a unique integer $y(x)$ in $\{0,1,\ldots, n-1\}$, and let $f(x)$ be the binary expansion of $y(x)$ [padding out the leading $0$s if need be so all strings are of length exactly $\lceil \log_2 n\rceil$]. Then each $x \in X$ is given a unique binary string $f(x)$ of length $r=\lceil \log_2 n \rceil$. Then define $S=\{Z_1,Z_2,\ldots, Z_r\}$ as follows: For each integer $i=1,2, \ldots, r$, the element $x$ is in $Z_i$ iff the $i$-th bit of $f(x)$ is $1$. You can check to see that this works.