18. (GDR 1) Let $N=\{1, 2, \cdots \cdots, n\}, n \geqslant 2$.
$F=\left\{A_{1}, \cdots, A_{\mathrm{t}}\right\}, A_{i} \subseteq N, i=1,2$. $\cdots, t$. If for every pair of elements $\{x, y\}$ in $N$, there exists $A_{i} \in F$ such that $A_{i} \cap\{x, y\}$ contains exactly one element, then $F$ is called separating. If every element of $N$ is contained in at least one $A_{i} \in F$, then $F$ is called covering. Find the minimum value of $t$ for $\left.\cdots, A_{1}\right\}$, denoted as $f(n)=?$
10. (Ji Zhu Germany 1)

Solution:
$$
f(m)=\left\{\begin{array}{ll}
{\left[\log _{2} n\right]+1,} & \text { if } n=2^{r} \\
{\left[\log _{2} n\right],} & \text { if } n \neq 2^{r}
\end{array}\right.
$$

There is a set $F=\left\{A_{1}, \cdots, A_{1}\right\}$ that is separating for an $n$-element set $N$ only when $n \leqslant 2$. This can be proven by induction. When $t=1$, it is obvious.

Assume $F=\left\{A_{1}, \cdots, A_{t}\right\}$ is separating for an $n$-element set when $n \geqslant 2^{t}+1$, then $F^{\prime}=\left\{A_{1}, \cdots, A_{t-1}\right\}$ is separating for $N^{\prime}=A_{1}$ and $N=N \backslash A_{t}$. This is a self-contradictory statement. Because
$$
\left|N^{\prime}\right|>2^{t-1} \text { or }\left|Y^{\prime \prime}\right|>2^{t-1} \text {. }
$$

Thus, a separating set must have at least $\left[\log _{2} n\right]$ elements, where $n=|N|$.

If $t=r$ and $n=2^{r}$, there is always exactly one element left uncovered. In fact:

Since $F$ is separating, there is at most one element not covered. The proof of its existence for $r \geqslant 1$ uses induction.
When $r=1$, it is obvious.
If $\left|A_{1}\right|>2^{\mathrm{r}-1}$, then $F-\left\{A_{1}\right\} \geqslant \log _{2}\left|A_{1}\right|$ gives
$$
t=F \geqslant t+1 \text {. }
$$

If $A_{1}<2^{\mathrm{r}-1}$, then $F-A_{1}$ separates $N-A_{1}$, and by the inductive hypothesis, there is an element $y \in N-A_{1}$ not covered, nor covered by $A_{1}$.
From (2) and (3), we get
$$
f(n) \geqslant\left\{\begin{array}{ll}
{\left[\log _{2} n\right]+1,} & n=2^{r}, \\
{\left[\log _{2} n\right],} & n \neq 2^{2} .
\end{array}\right.
$$

Construct a set $F$ that is both separating and covering for $N$, where $2^{\mathrm{r}-1}<n<2^{\mathrm{r}}, r \geqslant 1$. For $r=1$, take the set $A_{1}=\{1\}$.
From $r$ to $r+1$ for the proof: Let $N^{\prime}, N^{\prime \prime}$ be transformed sets, and $\left|N^{\prime}\right|=\left|N^{\prime \prime}\right|=2^{r}$, for $N^{\prime}$ (or $N^{\prime \prime}$) let $A_{1}^{\prime} \cdots A_{1}^{\prime}$ (correspondingly $A_{1}^{\prime \prime}, \cdots, A_{\mathrm{r}}^{\prime \prime}$) be the separating sets (for $r=1, \cdots, r$), and $f\left(N^{\prime}\right)$ (or $N^{\prime \prime}$) the uncovered element $y^{\prime}$ (correspondingly $y^{\prime \prime}$). The set $A_{r+1}=\left\{y^{\prime}\right\} \cup N^{\prime \prime} \backslash\left\{y^{\prime \prime}\right\}$.

Clearly, $F=\left\{A_{1}, \cdots, A_{\mathrm{r}+1}\right\}$ separates $N = N^{\prime} \cup N^{\prime \prime}$, and exactly leaves one uncovered element. This is a separating and covering set $F$ (with $|F|=r+1$). For $N$,
$$
A \subseteq N^{\prime} \cup N^{\prime \prime}\left(y^{\prime \prime} \in A\right) .
$$