Fang-jh: Which year's TST is this? I don't see any reason to require the sets $ A_i$ to be different, by the way. The condition $ a_i\geq 1$ is equally useless. darij

darij grinberg wrote: The proof is flawed. $ H_{A\cup B} = H_A\cup H_B$, not $ H_{A\cup B} = H_A\cap H_B$. Mind the difference between "do not contain $ A$" and "do not intersect $ A$". Fang-jh: Which year's TST is this? I don't see any reason to require the sets $ A_i$ to be different, by the way. The condition $ a_i\geq 1$ is equally useless. darij it is problem 3 of the fourth quiz of Chinese TST 2008 (March 22,2008)

Sorry for a potentially stupid question, but what is a "quiz"? Is it just a round of the TST, or is it something easier than the usual TST's? darij

darij grinberg wrote: Sorry for a potentially stupid question, but what is a "quiz"? Is it just a round of the TST, or is it something easier than the usual TST's? darij There are 6 quizzes in total, it is easier than the usual TST.

It directly follows from Kleitman lemma (which is itself quite subtle): If $ U$ and $ V$ are two collections of subsets of a set $ S$, each of them closed under taking subsets (i.e. $ A\in U$, $ B\subset A$ implies $ B\in A$) then $ |U\cap V|\ge |U|\cdot |V|/2^{|S|}$. That is, events ``to belong to $ U$'' and ``to belong to $ V$' for randomly chosen subset of $ S$ correlate positively (or how to say it?)

Incorrect, sorry: So let us consider a random subset $X$ of $S$ that is constructed by placing each element of $S$ in $X$ with probability $\frac{1}{2}$. Now, consider the probability that some specific $A_i$ is completely contained in $X$. That means for each $x \in A_i$, we must have placed $x$ in $X$, and this happens with probability $\frac{1}{2^{a_i}}$. Thus, the probability that $A_i$ is not completely contained in $X$ is $1 - \frac{1}{2^{a_i}}$. Thus, the probability that no $A_i$ is contained in $X$ is simply $ \prod_{i = 1}^k(1-\frac{1}{2^{a_{i}}}). $ But there are $2^n$ total subsets of $S$, and then the result follows. $\blacksquare$

TheStrangeCharm wrote: Thus These are not independent events!

JBL wrote: TheStrangeCharm wrote: Thus These are not independent events! Sure,you can't multiply them like this!

Sorry for reviving But is there any solution with expected value?

Take a random subset $U$ of $S$. Let $E_i\,,\,i=1,2,\dots,k$ be the event that $U$ doesn't contain $A_i$. We will prove $$P(E_1\cap E_2\cap\dots\cap E_k)\geq \prod_{i = 1}^k(1 - \frac {1}{2^{a_{i}}}).$$The proof goes by induction. We start with the equality: \[P(E_2\cap\dots\cap E_k)=P(E_1)P_{E_1}(E_2\cap\dots\cap E_k)+P(\overline{E_1})P_{\overline{E_1}}(E_2\cap\dots\cap E_k).\]It follows: \begin{align*}(*)\,\,\,\,\,\,\,\,\, P(E_1\cap\dots\cap E_k) &= P(E_1)P_{E_1}(E_2\cap\dots\cap E_k) = \\ &= P(E_2\cap\dots\cap E_k) - P(\overline{E_1})P_{\overline{E_1}}(E_2\cap\dots\cap E_k)\\ &\geq P(E_2\cap\dots\cap E_k)- P_{\overline{E_1}}(E_2\cap\dots\cap E_k). \end{align*} Let's consider the probability $P_{\overline{E_1}}(E_2\cap\dots\cap E_k)$. Let us denote $A'_i := A_i\setminus A_1\,,\,i=2,3,\dots,k$. We want to estimate the probability the random set $U$ to contain $A_1$ and $U_1 :=U\setminus A_1$ not to contain any $A'_i\,,\,i=2,\dots,k$. To each such $U_1$ corresponds $2^{a_1}$ sets $U :=U_1\cup U'$, where $U'\subset A_1$ not containing any $A'_i\,,\,i=2,\dots,k$. It means: $$P_{\overline{E_1}}(E_2\cap\dots\cap E_k) =2^{-a_1}P(E'_2\cap\dots\cap E'_k) \leq 2^{-a_1}P(E_2\cap\dots\cap E_k) $$Here the event $E'_i,i=2,\dots,k$ means the random set $U$ not to contain $A'_i$. Now, we use the induction hypothesis, so $P(A_2\cap\dots\cap A_k)\geq \prod_{i = 2}^k(1 - \frac {1}{2^{a_{i}}})$. Then $(*)$ yields: \[P(A_1\cap\dots\cap A_k)\geq \prod_{i = 2}^k(1 - \frac {1}{2^{a_{i}}}) (1-\frac{1}{2^{a_1}})=\prod_{i = 1}^k(1 - \frac {1}{2^{a_{i}}}).\]which completes the induction step.

$\textbf{Solution :}$ Induction on $\sum_{i\not= j} |A_i\cap A_j|$. Consider larger set $S':= S\cup\{n+1\} = [1, n+1]$ and same subsets $A_1,\ldots , A_k$ of it. So it's enough to prove that number of subsets of $S'$ that don't contain any $A_i$ is greater than or equal to $2^{n+1}\prod_{i=1}^k(1-\frac{1}{2^{a_i}})$. We can assume that $\exists a\in A_1\cap A_2$. Consider new subsets of $S'$ : $\{n+1\}\cup A_1\setminus\{a\}, A_2, A_3, \ldots , A_k$. Consider next numbers : 1) Let $X$ be number of subsets of $S'$ that don't contain any $A_i$. 2) Let $X_{n+1}^a$ be number of subsets of $S'$ that don't contain any $A_i$ and also don't contain element $n+1$ but contain element $a$. 3) Let $X_{a}^{n+1}$ be number of subsets of $S'$ that don't contain any $A_i$ and also don't contain element $a$ but contain element $n+1$. 4) Let $X_{n+1, a}$ be number of subsets of $S'$ that don't contain any $A_i$ and also don't contain elements $n+1, a$. 5) Let $X^{n+1, a}$ be number of subsets of $S'$ that don't contain any $A_i$, but contain elements $n+1, a$. 6) Let $Y$ be number of subsets of $S'$ that don't contain any $A_i$ for $i\not= 1$ and don't contain set $\{n+1\}\cup A_1\setminus\{a\}$. 7) Similarly define numbers $Y_{n+1}^a, Y_{a}^{n+1}, Y_{n+1, a}, Y^{n+1, a}$. By induction hypothesis we know that $Y \geq 2^{n+1}\prod_{i=1}^k(1-\frac{1}{2^{a_i}})$, so it's enough to prove that $X\geq Y$. $\textbf{Lemma 1 :}$ We get that $X_{a}^{n+1} + X_{n+1}^a\geq Y_{a}^{n+1} + Y_{n+1}^a$. $\textbf{Lemma 2 :}$ We get that $X_{n+1, a} = Y_{n+1, a}$. $\textbf{Lemma 3 :}$ We get that $X^{n+1, a} = Y^{n+1, a}$. Proofs of lemmas 1-3 is simple exercise. So, finally, we get that $X = (X_{a}^{n+1} + X_{n+1}^a) + X_{n+1, a} + X^{n+1, a}\geq (Y_{a}^{n+1} + Y_{n+1}^a) + Y_{n+1, a} + Y^{n+1, a}\geq 2^{n+1}\prod_{i=1}^k(1-\frac{1}{2^{a_i}})$. $\Box$

Here's a solution using a nuke. Theorem: (FKG Inequality) Let $X_1, \dots, X_n$ be decreasing functions on $\{0, 1\}^n$ (or any lattice). Then $\mathbb{E}[\prod X_i] \ge \prod \mathbb{E}[X_i].$ Now to finish use this inequality for the variables $X_i(S) = 0$ if $A_i \subseteq S$ and $1$ otherwise.

Keeping stuff low-powered, I guess. We begin with the key lemma. Lemma. If we replace any element $x$ in one of the $X_i$s with an element $y$ that does not appear in any of the other $X_i$s, then the number of subsets of $\{1,2,\cdots,n\}$ not containing any of the other $X_i$s does not increase. Proof. WLOG the $X_i$ having $x$ replaced with $y$ has index $1$. Consider the $X_i$: $X_1\setminus \{x\}, X_2, X_3, \ldots$. There are two classes of subsets of $\{1,2,\ldots,n\}$ that work for $(X_1\setminus \{x\})\sqcup \{y\}, X_2, \cdots, X_m$: Ones that also work $X_1\setminus \{x\}, X_2, X_3, \ldots$, and ones that do not. Notice that all of the subsets that work for $X_1\setminus \{x\}, X_2, X_3, \ldots$ also work for both $(X_1\setminus \{x\})\sqcup \{y\}, X_2, \cdots, X_m$ and $X_1,X_2,\cdots X_m$. Now, we look at the subsets that do not work for \[(X_1\setminus \{x\}), X_2, X_3\cdots, X_m\]but do work for $X_1, X_2, \cdots, X_m$. These subsets are exactly those which contain $X_1\setminus \{x\}$ that do not contain $x$ and $X_2, X_3, \cdots, X_m$. Similarly, we look at the subsets that do not work for \[(X_1\setminus \{x\}), X_2, X_3\cdots, X_m\]but do work for $(X_1\setminus \{x\})\sqcup \{y\}, X_2, X_3,\cdots, X_m$. These subsets are exactly those which contain $X_1\setminus \{x\}$ that do not contain $y$ and $X_2, X_3, \cdots, X_m$. Thus, it suffices to show that there are at least as many subsets that contain $X_1\setminus \{x\}$ that do not contain $x$ and $X_2, X_3, \cdots, X_m$ than those that contain $X_1\setminus \{x\}$ that do not contain $y$ and $X_2, X_3, \cdots, X_m$. But notice that if a subset contains both $x$ and $y$ or neither $x$ nor $y$ and works for the second case, it also works for the first case. If a subset $S$ contains only $x$ and works for the second case, then $(S\setminus \{x\})\sqcup \{y\}$ also works for the first case. Thus, the first is at least as large, and the proof of the Lemma is complete. Now, we show the problem for $\sum_i |X_i|\leq n$ and $|X_i|$ fixed for each $X_i$. Proof. If we have two equal numbers in two of the $X_i$, then we know that we can replace one of them with a number that does not appear in any of the $X_i$. By the size assumption, we won't run out of numbers, so the minimum number of subsets not containing any of the $X_i$ is attained when all of the $X_i$ are disjoint. Then, by a simple counting argument (e.g. using proportions, similar to the proof of the formula of Euler's Totient Function), we have the desired bound of \[2^n\cdot\prod_{i=1}^{m}\left(1-\frac{1}{2^{|X_i|}}\right).\] Finally, we show the problem for arbitrary fixed $|X_i|$. Let $N$ be a number larger than $\sum_{i}|X_i|$. Then, we have, for any choice of $X_i$, \begin{align*} \text{[\# subsets of $[n]$ not containing any $X_i$]} &= \frac{1}{2^{N-n}}\text{[\# subsets of $[N]$ not containing any $X_i$]}\\ &\geq \frac{1}{2^{N-n}}\cdot 2^N\cdot\prod_{i=1}^{m}\left(1-\frac{1}{2^{|X_i|}}\right)\\ & =2^n\cdot\prod_{i=1}^{m}\left(1-\frac{1}{2^{|X_i|}}\right) \end{align*}as requested. $\blacksquare$

Ha! This will be a good example to illustrate a basic spirit of probablistic method - making counting simpler!