The problem was posed by Katona (1973) and solved independently by Yao (1976) and Cai (1983), who obtained
where
is the ceiling function. is nondecreasing, and the values for , 2, ... are 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, ... (OEIS A007600).
The first arguments giving each successive value of are 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ... (OEIS A007601), so , as illustrated in the preceding example.
Cai, M.-C. "Solutions to Edmonds' and Katona's Problems on Families of Separating Subsets." Disc. Math.47, 13-21, 1983.
https://doi.org/10.1016/0012-365X(83)90068-7.Honsberger,
R. "Cai Mao-Cheng's Solution to Katona's Problem on Families of Separating Subsets."
Ch. 18 in Mathematical
Gems III. Washington, DC: Math. Assoc. Amer., pp. 224-239, 1985.Katona,
G. O. H. "Combinatorial Search Problems." In A
Survey of Combinatorial Theory (Ed. J. N. Srivastava, F. Harary, C. R.
Rao, G.-C. Rota, and S. S. Shrikhande). Amsterdam, Netherlands: North-Holland,
pp. 285-308, 1973.Sloane, N. J. A. Sequences A007600/M0456
and A007601/M0525 in "The On-Line Encyclopedia
of Integer Sequences."Vatter, V. "Maximal Independent Sets
and Separating Covers." Amer. Math. Monthly118, 418-423, 2011.
https://doi.org/10.4169/amer.math.monthly.118.05.418.Yao,
A. C. C. "On a Problem of Katona on Minimal Separating Systems."
Disc. Math.15, 193-199, 1976. https://doi.org/10.1016/0012-365X(76)90085-6.
of subsets in a separating
family for a set of 
elements, where a separating
family is a set of subsets
in which each pair of distinct elements is found separated,
each in one of two disjoint subsets. For example,
the 26 letters of the alphabet can be separated by a family of nine:
![f(n)=min{2p+3[log_3(n/(2^p))]:p=0,1,2},](/images/equations/KatonasProblem/NumberedEquation2.svg)
![[x]](/images/equations/KatonasProblem/Inline3.svg)
is the ceiling function. 
is nondecreasing, and the values for 
, 2, ... are 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, ... (OEIS A007600).
The first arguments giving each successive value of 
are 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ... (OEIS A007601), so 
, as illustrated in the preceding example.
