10. (GDR 1) Let . A collection of subsets , is said to be separating if for every pair , there is a set such that contains just one element. A collection is said to be covering if every element of is contained in at least one set . What is the smallest value of such that there is a set that is simultaneously separating and covering?
Solution
10. We claim that if the family separates the -set , then . The proof goes by induction. The case is clear, so suppose that the claim holds for . Since does not separate elements of its own or its complement, it follows that is separating for both and , so that . Then , as claimed. Also, if the set with is separated by , then (precisely) one element of is not covered. To show this, we again use induction. This is trivial for , so let . Since separate both and must have exactly elements, and thus one of its elements is not covered by , and neither is covered by . We conclude that a separating and covering family of subsets can exist only if . We now construct such subsets for the set if . For , put . In the step from to , let , where ; let be subsets covering and separating and such subsets for . Then the subsets and obviously separate and cover . The answer: . Second solution. Suppose that the sets cover and separate . Label each element with a string of of 0 's and 1's, where is 1 when otherwise. Since the 's separate, these strings are distinct; since they cover, the string ( ) does not occur. Hence . Conversely, for , represent the elements of in base 2 as strings of 0's and 1's of length . For , take to be the set of numbers in whose binary string has a 1 in the th place. These sets clearly cover and separate.