L OM - I - Problem 8

Given a natural number $ n \geq 2 $ and an $ n $-element set $ S $. Determine the smallest natural number $ k $ for which there exist subsets $ A_1, A_2, \ldots, A_k $ of the set $ S $ with the following property:
for any two distinct elements $ a, b \in S $, there exists a number $ j \in \{1, 2, \ldots, k\} $ such that the set $ A_j \cap \{a, b\} $ is a singleton.
We will show that $ k = [\log_2(n-1) +1] $, i.e., $ 2^{k-1} < n \leq 2^k $.
Given the number $ k $ defined as above, we construct sets $ A_j $ as follows: we number the elements of set $ S $ with $ k $-digit binary numbers (leading zeros are allowed). We thus have $ 2^k \geq n $ numbers available. Then, we take $ A_i $ to be the set of elements of $ S $ whose number has a 1 in the $ i $-th position. Any two different elements $ a $ and $ b $ of set $ S $ are then assigned different numbers, which differ, say, in the $ j $-th position. In this case, exactly one of the elements $ a $, $ b $ belongs to the set $ A_j $.
The number $ k $ found in this way is the smallest. Suppose, for instance, that there exist sets $ A_1, A_2, \ldots, A_k $ satisfying the conditions of the problem for $ 2^k < n $. We assign to each element $ x $ of set $ S $ a sequence of $ k $ numbers $ (c_1, c_2, \ldots, c_k) $ according to the following rule:






Since $ 2^k < n $, there exist two different elements $ a, b \in S $ that are assigned the same sequence of numbers. This means that element $ a $ belongs to exactly the same sets among $ A_1, A_2, \ldots, A_k $ as element $ b $.