Let $n$ be a positive integer and let $\mathcal{A}$ be a family of non-empty subsets of $\{1, 2, \ldots, n \}$ such that if $A \in \mathcal{A}$ and $A$ is subset of a set $B\subseteq \{1, 2, \ldots, n\}$, then $B$ is also in $\mathcal{A}$. Show that the function $$f(x):=\sum_{A \in \mathcal{A}} x^{|A|}(1-x)^{n-|A|}$$is strictly increasing for $x \in (0,1)$.
Problem
Source: Bulgarian Winter Tournament 2024 12.3
Tags: combinatorics, probability
28.01.2024 16:21
Wow, this problem is cool. Let's create a random subset of $[n]$ by including each $k=1,2,\ldots,n$ independently, with probability $x\in(0,1).$ Then, $f(x)$ denotes the probability that the set we've created belongs to $\mathcal{A}.$ Notice that because $\mathcal{A}$ is an upset, then there exists a collection of sets $K_1,\ldots,K_m$ with the property that $S\in\mathcal{A}$ if and only if $K_i\subseteq S$ for some $i=1,\ldots,m.$ Consequently, letting $E_i$ be the event that $K_i\subseteq S$ and given that $P(K\subseteq S)=x^{|K|}$ it follows by PIE that \[f(x)=P\left(\bigcup_{i=1}^m E_i\right)=\sum_{t=1}^m\sum_{i_1,\ldots,i_t} P\left(\bigcap_{j=1}^tE_{i_j}\right)(-1)^{t+1}=\sum_{t=1}^m\sum_{i_1,\ldots,i_t}x^{|K_{i_1}\cap\hspace{1pt}\cdots\hspace{1pt}\cap\hspace{1pt}K_{i_t}|}(-1)^{t+1}.\]To show that $f(x)$ is increasing, it suffices to show that $f'(x)\geqslant 0$ which is equivalent to \[\sum_{t=1}^m\sum_{i_1,\ldots,i_t}|K_{i_1}\cap\cdots\cap K_{i_t}|\cdot x^{|K_{i_1}\cap\hspace{1pt}\cdots\hspace{1pt}\cap\hspace{1pt}K_{i_t}|}(-1)^{t+1}\geqslant 0.\]Now, the key is to reinterpret $|K_{i_1}\cap\cdots\cap K_{i_t}|.$ For each $k=1,\ldots,n$ let $\mathcal{A}_k$ be the set of indices $i{}$ for which $k\in K_i.$ Let $\chi_S(x)$ be the characteristic function of $x\in S.{}$ Of course, $k\in K_{i_1}\cap\cdots\cap K_{i_t}$ if and only if $K_{i_1},\ldots,K_{i_t}\in \mathcal{A}_k.$ Thus\begin{align*}f'(x)&=\sum_{t=1}^m\sum_{i_1,\ldots,i_t}\Bigg(\sum_{i=1}^n\chi_i(K_{i_1}\cap\cdots\cap K_{i_t})\Bigg) x^{|K_{i_1}\cap\hspace{1pt}\cdots\hspace{1pt}\cap\hspace{1pt}K_{i_t}|}(-1)^{t+1} \\ &=\sum_{i=1}^n\Bigg(\sum_{t=1}^{|\mathcal{A}_i|}\sum_{\substack{i_1,\ldots,i_t \\ i_j\in\mathcal{A}_i}}x^{|K_{i_1}\cap\hspace{1pt}\cdots\hspace{1pt}\cap\hspace{1pt}K_{i_t}|}(-1)^{t+1}\Bigg)=\sum_{i=1}^n P\left(\bigcup_{j\in\mathcal{A}_i}E_j\right)\geqslant 0.\end{align*}Remarks. This looks approachable using the Ahlswede-Daykin theorem or perhaps the Fortuin-Kasteleyn-Ginibre inequality. I'm really curious to see if there are any solution involving these reuslts, or at least motivational arguments.
28.01.2024 17:59
Isn't it much easier? If we increase the probability $x$, we can interpret this as first choosing the element with probability $x$, and then choosing the element (if not yet chosen) with another given (conditional) probability. But realizing both stochastic experiments in this way on the same probability space, we always get a superset of the set with the smaller probability for the larger probability. But since our family contains all supersets of its elements, the conclusion now follows immediately.
30.01.2024 22:53
Fun fact, me and the proposer knew a nice non-olympiad original source of this problem, but I just unexpectedly heard about the coincidence with VJIMC 2007 Category 2 Problem 4