Problem 991

［Solution 1］Let $n=2^{r}$ and define
$$\begin{aligned} A_{1}= & \left\{1,2, \cdots, 2^{r-1}\right\}, \\ A_{2}= & \left\{1,2, \cdots, 2^{r-2}, 2^{r-1}+1,2^{r-1}+2, \cdots, 2^{r-1}+2^{r-2}\right\}, \\ A_{3}= & \left\{1,2, \cdots, 2^{r-3}, 2^{r-2}+1,2^{r-2}+2, \cdots, 2^{r-2}+2^{r-3}, 2^{r-1}+1,2^{r-1}\right. \\ & +2, \cdots, 2^{r-1}+2^{r-3}, 2^{r-1}+2^{r-2}+1,2^{r-1}+2^{r-2}+2, \cdots, 2^{r-1} \\ & \left.+2^{r-2}+2^{r-3}\right\}, \end{aligned}$$
$$\begin{array}{l} \vdots \\ A_{r-1}=\left\{1,2,5,6,9,10, \cdots, 2^{t}-3,2^{t}-2\right\}, \\ A_{r}=\left\{1,3,5,7, \cdots, 2^{t}-3,2^{t}-1\right\} . \end{array}$$

It is easy to see that $F=\left\{A_{1}, A_{2}, \cdots, A_{r}\right\}$ distinguishes $S$ and $U_{i=1}^{r} A_{i}=\left\{1,2, \cdots, 2^{r}-1\right\}=\{1$, $2, \cdots, n-1\}$. Clearly, adding just one more set $A_{0}=\{n\}$ to $F$ will cover $S$. Therefore, we have
$$f(n) \leqslant r+1=\left[\log _{2} n\right]+1 .$$

When $2^{r-1}+1 \leqslant n \leqslant 2^{r}-1$, $F$ itself (possibly intersected with $S$) is both distinguishing and covering $S$, so (1) still holds.
On the other hand, we use mathematical induction to prove the reverse inequality of (1):
$$f(n) \geqslant r+1 \text {, when } 2^{r} \leqslant n \leqslant 2^{r+1}-1$$

By $f(2)=f(3)=2$, we know that (2) holds for $r=1$. Assume (2) holds for $r=k$. When $r=$ $k+1$, let $F=\left\{A_{0}, A_{1}, \cdots, A_{t}\right\}$ be both distinguishing and covering $S$. Let $A^{\prime}{ }_{0}=S-A_{0}$, then $\left|A_{0}\right|+\left|A^{\prime}{ }_{0}\right|=n$, without loss of generality, assume $\left|A_{0}\right| \geqslant\left[\frac{n}{2}\right]$. At this time, $\left\{A_{1} \cap A_{0}, A_{2} \cap\right.$ $\left.A_{0}, \cdots, A_{t} \cap A_{0}\right\}$ is both distinguishing and covering $A_{0}$. Therefore, by the induction hypothesis, $t \geqslant$ $f\left(\left[\frac{n}{2}\right]\right) \geqslant k+1$. Thus, (2) also holds for $r=k+1$.
In summary, $f(n)=\left[\log _{2} n\right]+1$.
[Solution 2] Let $F=\left\{A_{1}, A_{2}, \cdots, A_{t}\right\}$ be both distinguishing and covering $S$. Consider the relation table of the subsets $A_{i}$ of $S$ and the elements
where
$$x_{i j}=\left\{\begin{array}{l} 1, \text { when } i \in A_{j}, \\ 0, \text { when } i \notin A_{j}, \end{array} \quad i=1,2, \cdots, n, j=1,2, \cdots, t .\right.$$

Since $F$ is covering, each element $i$ belongs to at least one $A_{j}$, i.e., each row in the table is not all 0; since $F$ is distinguishing, no two rows in the table are identical. Since there are $2^{t}-1$ different non-zero vectors of $t$ components, each of which is 0 or 1, we have
$$n \leqslant 2^{t}-1 \text {. }$$

Thus, we get
$$f(n) \geqslant\left[\log _{2} n\right]+1 .$$

On the other hand, for $n \in N$, take $t \in N$ such that $2^{t-1} \leqslant n \leqslant 2^{t}-1$ and take $n$ different non-zero $t$-vectors:
$$\left(x_{i 1}, x_{i 2}, \cdots, x_{i t}\right), i=1,2, \cdots, n,$$

where $x_{i j}$ are all 0 or 1. Define the subset $A_{j} \subset S$ as follows: for each $i \in S$, $i \in A_{j}$ if and only if $x_{i j}=1$, $j=1,2, \cdots, t$. It is easy to verify that $F=\left\{A_{1}, A_{2}, \cdots, A_{t}\right\}$ is both distinguishing and covering $S=\{1,2, \cdots, n\}$. Therefore, we get
$$f(n) \leqslant t=\left[\log _{2} n\right]+1 .$$

From (3) and (4), we have $f(n)=\left[\log _{2} n\right]+1$.