10. (GDR 1) Let $N=\{1,2, \ldots, n\}, n \geq 2$. A collection $F=\left\{A_{1}, \ldots, A_{t}\right\}$ of subsets $A_{i} \subseteq N, i=1, \ldots, t$, is said to be separating if for every pain $\{x, y\} \subseteq N$, there is a set $A_{i} \in F$ such that $A_{i} \cap\{x, y\}$ contains just one element. A collection $F$ is said to be conering if every element of $N$ is contained in at least one set $A_{i} \in F$. What is the smallest value $f(n)$ of $t$ such that there is a set $F=\left\{A_{1}, \ldots, A_{t}\right\}$ that is simultaneously separating and covering?
10. We claim that if the family $\left\{A_{1}, \ldots, A_{t}\right\}$ separates the $n$-set $N$, then $2^{t} \geq n$. The proof goes by induction. The case $t=1$ is clear, so suppose that the claim holds for $t-1$. Since $A_{1}$ does not separate elements of its own or its complement, it follows that $\left\{A_{1}, \ldots, A_{t-1}\right\}$ is separating for both $A_{i}$ and $N \backslash A_{i}$, so that $\left|A_{t}\right|,\left|N \backslash A_{t}\right| \leq 2^{t-1}$. Then $|N| \leq 2-2^{t-1}=2^{t}$, as claimed.
Also, if the set $N$ with $N=2^{t}$ is separated by $\left\{A_{1}, \ldots, A_{t}\right\}$, then (precisely) one element of $N$ is not covered. To show this, we again use induction. This is trivial for $t=1$, so let $t \geq 1$. Since $A_{1}, \ldots, A_{t-1}$ separate both $A_{t}$ and $N \backslash A_{t}, N \backslash A_{t}$ must have exactly $2^{t-1}$ elements, and thus one of its elements is not covered by $A_{1}, \ldots, A_{t-1}$, and neither is covered by $A_{\mathrm{f}}$. We conclude that a separating and covering family of $t$ subsets can exist only if $n \leq 2^{t}-1$.
We now construct such subsets for the set $N$ if $2^{t-1} \leq n \leq 2^{t}-1, t \geq 1$. For $t=1$, put $A_{1}=\{1\}$. In the step from $t$ to $t+1$, let $N=N^{\prime} \cup N^{\prime \prime} \cup\{y\}$, where $\left|N^{\prime}\right|,\left|N^{\prime \prime}\right| \leq 2^{\mathrm{t}-1}$; let $A_{1}^{\prime}, \ldots, A_{t}^{\prime}$ be subeets covering and separating $N^{\prime}$ and $A_{1}^{\prime \prime}, \ldots, A_{i}^{\prime \prime}$ such subsets for $N^{\prime \prime}$. Then the subsets $A_{i}=A_{i}^{\prime} \cup A_{i}^{\prime \prime}$ $(i=1, \ldots, t)$ and $A_{t+1}=N^{\prime \prime} \cup\{y\}$ obviously separate and cover $N$. The answer: $t=\left[\log _{2} n\right]+1$.
Second solution. Suppose that the sets $A_{1}, \ldots, A_{t}$ cover and separate $N$. Label each element $x \in N$ with a string of ( $\left.x_{1} x_{2} \ldots x_{t}\right)$ of 0 's and 1's. where $x_{i}$ is 1 when $x \in A_{i}, 0$ otherwise. Since the $A_{i}$ 's separate, these strings are distinct; since they cover, the string ( $00 \ldots 0)$ does not occur.

Hence $n \leq 2^{t}-1$. Conversely, for $2^{t-1} \leq n<2^{t}$, represent the elements of $N$ in base 2 as strings of 0 's and 1's of length $t$. For $1 \leq i \leq t$, take $A_{i}$ to be the set of numbers in $N$ whose binary string has a 1 in the ith place. These sets clearly cover and separate.