MathDB

10

Part of 1988 IMO Shortlist

Problems(1)

Simultaneously separating and covering

Source: IMO ShortList 1988, Problem 10, East Germany 1, Problem 18 of ILL

10/22/2005
Let N \equal{} \{1,2 \ldots, n\}, n \geq 2. A collection F \equal{} \{A_1, \ldots, A_t\} of subsets Ai⊆N, A_i \subseteq N, i \equal{} 1, \ldots, t, is said to be separating, if for every pair {x,y}⊆N, \{x,y\} \subseteq N, there is a set Ai∈F A_i \in F so that Ai∩{x,y} A_i \cap \{x,y\} contains just one element. F F is said to be covering, if every element of N N is contained in at least one set Ai∈F. A_i \in F. What is the smallest value f(n) f(n) of t, t, so there is a set F \equal{} \{A_1, \ldots, A_t\} which is simultaneously separating and covering?
combinatoricsSet systemsExtremal combinatoricsIMO Shortlist