Problem A. 811. (November 2021)
A. 811. Let \(\displaystyle A\) be a given set with \(\displaystyle n\) elements. Let \(\displaystyle k<n\) be a given positive integer. Find the maximum value of \(\displaystyle m\) for which it is possible to choose sets \(\displaystyle B_i\) and \(\displaystyle C_i\) for \(\displaystyle i=1,2,\dots,m\) satisfying the following conditions:
\(\displaystyle (i)\) \(\displaystyle B_i \subset A\), \(\displaystyle |B_i|=k\),
\(\displaystyle (ii)\) \(\displaystyle C_i \subset B_i\) (there is no additional condition for the number of elements in \(\displaystyle C_i\)),
\(\displaystyle (iii)\) \(\displaystyle B_i \cap C_j \ne B_j \cap C_i\) for all \(\displaystyle i \ne j\).
(7 pont)
Deadline expired on December 10, 2021.
Solution. The maximum value of \(\displaystyle m\) is \(\displaystyle 2^k\).
Lower bound: it is easy to show a construction for \(\displaystyle 2^k\). Let \(\displaystyle B \subset A\) be a subset of \(\displaystyle k\) elements. For each \(\displaystyle 1 \leq i \leq 2^k\) let \(\displaystyle B_i=B\), and let \(\displaystyle C_i\) be all possible subsets of \(\displaystyle B\). It is easy to check that the conditions in the problem are satisfied.
Upper bound: let us prove that for any system of sets satisfying the conditions of the problem \(\displaystyle m \leq 2^k\). Let us assign integers from \(\displaystyle 1\) to \(\displaystyle n\) to the elements of set \(\displaystyle A\). For each \(\displaystyle 1 \leq i \leq m\) let \(\displaystyle S_i\) be the set of those \(\displaystyle 0-1\) sequences of length \(\displaystyle n\) in which the \(\displaystyle l^{th}\) digit is \(\displaystyle 1\), if \(\displaystyle l \in C_i\), and \(\displaystyle 0\), if \(\displaystyle l \in B_i \setminus C_i\). And if \(\displaystyle l \notin B_i\), then the digit can be arbitrary. Thus \(\displaystyle |S_i|=2^{n-k}\), because the value is given at \(\displaystyle k\) places, and arbitrary at \(\displaystyle n-k\) places.
Note that condition \(\displaystyle B_i \cap C_j \neq B_j \cap C_i\) means that if \(\displaystyle a \in S_i\) and \(\displaystyle b \in S_j\), then \(\displaystyle a \neq b\). Indeed, there must exist a number \(\displaystyle l\) for which \(\displaystyle l \in B_i \cap B_j\), and it contained in exactly one of \(\displaystyle C_i\) and \(\displaystyle C_j\), thus \(\displaystyle a\) and \(\displaystyle b\) will differ from each other at the \(\displaystyle l^{th}\) digit.
The number of \(\displaystyle 0-1\) sequences of length \(\displaystyle n\) is \(\displaystyle 2^n\), sets \(\displaystyle S_i\) are pairwise disjoint, and each has cardinality \(\displaystyle 2^{n-k}\), thus their number
\(\displaystyle m \leq \frac{2^n}{2^{n-k}}=2^k.\)
Statistics:
4 students sent a solution. 7 points: Móra Márton Barnabás. 6 points: Kovács 129 Tamás. 1 point: 2 students.
Problems in Mathematics of KöMaL, November 2021