Problem A. 847. (February 2023)
A. 847. Let \(\displaystyle A\) be a given finite set with some of its subsets called pretty. Let a subset be called small, if it's a subset of a pretty set. Let a subset be called big, if it has a pretty subset. (A set can be small and big simultaneously, and a set can be neither small nor big.) Let \(\displaystyle a\) denote the number of elements of \(\displaystyle A\), and let \(\displaystyle p\), \(\displaystyle s\) and \(\displaystyle b\) denote the number of pretty, small and big sets, respectively. Prove that \(\displaystyle 2^a\cdot p\le s \cdot b\).
Proposed by András Imolay, Budapest
(7 pont)
Deadline expired on March 10, 2023.
The problem is proved by induction on \(\displaystyle a\). If \(\displaystyle a=1\) then the statement is obviously true.
For the induction step, suppose that the base set \(\displaystyle A\) with element \(\displaystyle a>1\) has some nice subsets, denote their family by \(\displaystyle \mathcal{S}\). Let \(\displaystyle \mathcal{N}\) be the family of large subsets, i.e., containing an element in \(\displaystyle \mathcal{S}\), and \(\displaystyle \mathcal{K}\) be the family of small subsets, i.e., subsets of some set in \(\displaystyle \mathcal{S}\). We want to prove that
\(\displaystyle 2^a \cdot |\mathcal{S}| \leq |\mathcal{K}| \cdot |\mathcal{N}|,\)
if we know that the statement is true for arbitrary nice sets on a base set with less than \(\displaystyle a\) elements.
Let \(\displaystyle x \in A\) be an arbitrary element. Consider the following partitions of the sets given above:
\(\displaystyle \mathcal{S}_0=\{S \in \mathcal{S} \ | \ x \notin S\} \quad \text{ and } \quad \mathcal{S}_1=\{S \in \mathcal{S} \ | \ x \in S\},\)
\(\displaystyle \mathcal{K}_0=\{K \in \mathcal{K} \ | \ x \notin K\} \quad \text{ and } \quad \mathcal{K}_1=\{K \in \mathcal{K} \ | \ x \in K\},\)
\(\displaystyle \mathcal{N}_0=\{N \in \mathcal{N} \ | \ x \notin N\} \quad \text{ and } \quad \mathcal{N}_1=\{N \in \mathcal{N} \ | \ x \in N\}.\)
Furthermore, let us introduce the notation that if every element of a family \(\displaystyle \mathcal{Z}\) contains \(\displaystyle x\), then we denote by \(\displaystyle \mathcal{Z}'\) the family \(\displaystyle \{Z \setminus \{x\} \ | \ Z \in \mathcal{Z}\}\) on the base set \(\displaystyle A \setminus \{x\}\).
The main idea of the solution is to apply the induction hypothesis on the base set \(\displaystyle A \setminus \{x\}\) to the nice sets \(\displaystyle \mathcal{S}_0\), and also to the nice sets \(\displaystyle \mathcal{S}'_1\). From these we obtain some inequalities, from which we will finish the proof.
For shorter notation, the number of elements of each set is denoted by the corresponding lower case letter, i.e. \(\displaystyle |\mathcal{A}|=a\), \(\displaystyle |\mathcal{S}_0|=s_0\), \(\displaystyle |\mathcal{S}_1|=s_1\), \(\displaystyle |\mathcal{K}_0|=k_0\), \(\displaystyle |\mathcal{K}_1|=k_1\), \(\displaystyle |\mathcal{N}_0|=n_0\), \(\displaystyle |\mathcal{N}_1|=n_1\). So we have to prove that
\(\displaystyle 2^{a} \cdot (s_0+s_1) \leq (k_0+k_1)(n_0+n_1).\)
We first prove the following four inequalities:
\(\displaystyle 2^{a-1}s_0 \leq n_0k_0,\)
\(\displaystyle 2^{a-1}s_0 \leq n_1k_0,\)
\(\displaystyle 2^{a-1}s_1 \leq n_1k_0,\)
\(\displaystyle 2^{a-1}s_1 \leq n_1k_1.\)
In fact, they are all simple consequences of the induction hypothesis:
Consider the nice sets \(\displaystyle \mathcal{S}_0\) on the base set \(\displaystyle A \setminus \{x\}\). Then here the family of large sets is just \(\displaystyle \mathcal{N}_0\), while the family of small sets is a subset of \(\displaystyle \mathcal{K}_0\). Thus the first inequality follows immediately from the induction hypothesis. Furthermore, \(\displaystyle \mathcal{N}'_1\) contains the large sets, which gives the second inequality.
In a similar way, on the base set \(\displaystyle A \setminus \{x\}\), given the nice sets \(\displaystyle \mathcal{S}'_1\), the family of small sets is just \(\displaystyle \mathcal{K}'_1\), which contains \(\displaystyle \mathcal{K}_0\), and \(\displaystyle \mathcal{N}'_1\) contains the large sets, so applying the induction hypothesis to this gives the third and fourth inequalities.
If \(\displaystyle n_1k_0 \leq n_0k_1\), then adding the four proved inequalities and applying this to the inequality proves the statement. For this reason we can assume that \(\displaystyle n_1 \neq 0\) and \(\displaystyle k_0 \neq 0\). Thus, using the first and last inequalities
\(\displaystyle (k_0+k_1)(n_0+n_1) \geq \left(k_0+\frac{2^{a-1}s_1}{n_1}\right)\left(\frac{2^{a-1}s_0}{k_0}+n_1\right)=2^{a-1}s_0+k_0n_1+\frac{2^{2a-2}s_0s_1}{k_0n_1}+2^{a-1}s_1,\)
so it is sufficient to prove that
\(\displaystyle k_0n_1+\frac{2^{2a-2}s_0s_1}{k_0n_1} \geq 2^{a-1}(s_0+s_1).\)
After rearranging we get that it is enough to prove that
\(\displaystyle (k_0n_1)^2+2^{2a-2}s_0s_1-2^{a-1}(s_0+s_1)k_0n_1=(k_0n_1-2^{a-1}s_0)(k_0n_1-2^{a-1}s_1) \geq 0,\)
which is clear from the second and third inequalities. We are done.
Statistics:
4 students sent a solution. 7 points: Sida Li. 0 point: 3 students.
Problems in Mathematics of KöMaL, February 2023