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