A family $\mathcal F = \{F_1, \ldots, F_m\}$ of subsets of $\{1,2,\ldots,n\}$ is said to be separating if for any two elements $1 \leq i < j \leq n$, there is some set $F \in \mathcal F$ such that $|F\cap\{i,j\}| = 1$;
(a) Prove that the smallest separating family has size $\lceil \log_2n\rceil$.
The family is said to be strongly separating if even more is true: for every $1 \leq i < j \leq n$, there are sets $F,G \in \mathcal F$ such that $F\cap\{i,j\}= \{i\}, G\cap\{i,j\}= \{j\}$.
(b) Prove that the smallest strongly separating family has size $m$, where $m$ is the smallest natural number satisfying ${m}\choose{\lceil m/2\rceil}$.
I tried to prove part a) using contradiction but it does not work. I even do not know where can I start. Maybe some sort of Pigeon hole principle but I could not figure it out. Can anyone give me some hints? Thank you in advance!
You need to prove $m \ge \lceil \log_2n \rceil$. Because $m$ is an integer, this is equivalent to $m \ge \log_2n$, or $2^m \ge n$. When you have a power of $2$, think subsets. In this case, subsets of $\cal F$. Hint: let $S(i)$ be the set of subsets from $\cal F$ that contain $i$. How can you rewrite the condition "there is some set $F \in \cal F$ such that $|F\cap\{i,j\}|=1$" in terms of $S$?
For the second part, think about subsets too. What is the meaning of binomial coefficient $\binom a b$?