Maths Olympiad Prep

Library / /326 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

10. (GDR 1) Let N={1,2,,n},n2N=\{1,2, \ldots, n\}, n \geq 2. A collection F={A1,,At}F=\left\{A_{1}, \ldots, A_{t}\right\} of subsets AiN,i=1,,tA_{i} \subseteq N, i=1, \ldots, t, is said to be separating if for every pair {x,y}N\{x, y\} \subseteq N, there is a set AiFA_{i} \in F such that Ai{x,y}A_{i} \cap\{x, y\} contains just one element. A collection FF is said to be covering if every element of NN is contained in at least one set AiFA_{i} \in F. What is the smallest value f(n)f(n) of tt such that there is a set F={A1,,At}F=\left\{A_{1}, \ldots, A_{t}\right\} that is simultaneously separating and covering?

A number or a short expression. Spacing and $ signs are ignored.

Solution

10. We claim that if the family {A1,,At}\left\{A_{1}, \ldots, A_{t}\right\} separates the nn-set NN, then 2tn2^{t} \geq n. The proof goes by induction. The case t=1t=1 is clear, so suppose that the claim holds for t1t-1. Since AtA_{t} does not separate elements of its own or its complement, it follows that {A1,,At1}\left\{A_{1}, \ldots, A_{t-1}\right\} is separating for both AtA_{t} and N\AtN \backslash A_{t}, so that At,N\At2t1\left|A_{t}\right|,\left|N \backslash A_{t}\right| \leq 2^{t-1}. Then N22t1=2t|N| \leq 2 \cdot 2^{t-1}=2^{t}, as claimed. Also, if the set NN with N=2t|N|=2^{t} is separated by {A1,,At}\left\{A_{1}, \ldots, A_{t}\right\}, then (precisely) one element of NN is not covered. To show this, we again use induction. This is trivial for t=1t=1, so let t1t \geq 1. Since A1,,At1A_{1}, \ldots, A_{t-1} separate both AtA_{t} and N\At,N\AtN \backslash A_{t}, N \backslash A_{t} must have exactly 2t12^{t-1} elements, and thus one of its elements is not covered by A1,,At1A_{1}, \ldots, A_{t-1}, and neither is covered by AtA_{t}. We conclude that a separating and covering family of tt subsets can exist only if n2t1n \leq 2^{t}-1. We now construct such subsets for the set NN if 2t1n2t1,t12^{t-1} \leq n \leq 2^{t}-1, t \geq 1. For t=1t=1, put A1={1}A_{1}=\{1\}. In the step from tt to t+1t+1, let N=NN{y}N=N^{\prime} \cup N^{\prime \prime} \cup\{y\}, where N,N2t1\left|N^{\prime}\right|,\left|N^{\prime \prime}\right| \leq 2^{t-1}; let A1,,AtA_{1}^{\prime}, \ldots, A_{t}^{\prime} be subsets covering and separating NN^{\prime} and A1,,AtA_{1}^{\prime \prime}, \ldots, A_{t}^{\prime \prime} such subsets for NN^{\prime \prime}. Then the subsets Ai=AiAiA_{i}=A_{i}^{\prime} \cup A_{i}^{\prime \prime} (i=1,,t)(i=1, \ldots, t) and At+1=N{y}A_{t+1}=N^{\prime \prime} \cup\{y\} obviously separate and cover NN. The answer: t=[log2n]+1t=\left[\log _{2} n\right]+1. Second solution. Suppose that the sets A1,,AtA_{1}, \ldots, A_{t} cover and separate NN. Label each element xNx \in N with a string of (x1x2xt)\left(x_{1} x_{2} \ldots x_{t}\right) of 0 's and 1's, where xix_{i} is 1 when xAi,0x \in A_{i}, 0 otherwise. Since the AiA_{i} 's separate, these strings are distinct; since they cover, the string ( 00000 \ldots 0 ) does not occur. Hence n2t1n \leq 2^{t}-1. Conversely, for 2t1n<2t2^{t-1} \leq n<2^{t}, represent the elements of NN in base 2 as strings of 0's and 1's of length tt. For 1it1 \leq i \leq t, take AiA_{i} to be the set of numbers in NN whose binary string has a 1 in the ii th place. These sets clearly cover and separate.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.