IMO 1988 SL 10

Let N = {1, 2, . . ., n}, n \geq2. A collection F = {A1, . . . , At}

imoshortlistmathematicsolympiad

IMO 1988 SL 10

Origin: GDR

Problem

Let N = {1, 2, . . ., n}, n \geq2. A collection F = {A1, . . . , At} of subsets Ai \subseteqN, i = 1, . . . , t, is said to be separating if for every pair {x, y} \subseteqN, there is a set Ai \inF such that Ai \cap{x, y} contains just one element. A collection F is said to be covering if every element of N is contained in at least one set Ai \inF. What is the smallest value f(n) of t such that there is a set F = {A1, . . . , At} that is simultaneously separating and covering?

Solution

We claim that if the family {A1, . . . , At} separates the n-set N, then 2t \geqn. The proof goes by induction. The case t = 1 is clear, so suppose that the claim holds for t −1. Since At does not separate elements of its own or its complement, it follows that {A1, . . . , At−1} is separating for both At and N∖At, so that |At|, |N∖At| \leq2t−1. Then |N| \leq2\cdot2t−1 = 2t, as claimed. Also, if the set N with N = 2t is separated by {A1, . . . , At}, then (pre- cisely) one element of N is not covered. To show this, we again use in- duction. This is trivial for t = 1, so let t \geq1. Since A1, . . . , At−1 separate both At and N ∖At, N ∖At must have exactly 2t−1 elements, and thus one of its elements is not covered by A1, . . . , At−1, and neither is covered by At. We conclude that a separating and covering family of t subsets can exist only if n \leq2t −1. We now construct such subsets for the set N if 2t−1 \leqn \leq2t −1, t \geq1. For t = 1, put A1 = {1}. In the step from t to t+1, let N = N ′\cupN ′′\cup{y}, where |N ′|, |N ′′| \leq2t−1; let A′ 1, . . . , A′ t be subsets covering and separating N ′ and A′′ 1, . . . , A′′ t such subsets for N ′′. Then the subsets Ai = A′ i \cupA′′ i (i = 1, . . . , t) and At+1 = N ′′ \cup{y} obviously separate and cover N. The answer: t = [log2 n] + 1. Second solution. Suppose that the sets A1, . . . , At cover and separate N. Label each element x \inN with a string of (x1x2 . . . xt) of 0’s and 1’s, where xi is 1 when x \inAi, 0 otherwise. Since the Ai’s separate, these strings are distinct; since they cover, the string (00 . . . 0) does not occur.

Hence n \leq2t −1. Conversely, for 2t−1 \leqn < 2t, represent the elements of N in base 2 as strings of 0’s and 1’s of length t. For 1 \leqi \leqt, take Ai to be the set of numbers in N whose binary string has a 1 in the ith place. These sets clearly cover and separate.