Find the minimum number 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 adjacent 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:

The problem was posed by Katona (1973) and solved by C. Mao-Cheng in 1982,

where is the Ceiling Function. is nondecreasing, and the values for , 2, ... are 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, ... (Sloane's A007600). The values at which increases are 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ... (Sloane's A007601), so , as illustrated in the preceding example.

**References**

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 Problem.'' In *A Survey of Combinatorial Theory* (Ed. J. N. Srivasta
*et al.*). Amsterdam, Netherlands: North-Holland, pp. 285-308, 1973.

Sloane, N. J. A. Sequences
A007600/M0456
and A007601/M0525
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.
*The Encyclopedia of Integer Sequences.* San Diego: Academic Press, 1995.

© 1996-9

1999-05-26