Library / Bulgarian Winter Tournament /5 of 15

Bulgarian Winter Tournament

Combinatorics Difficulty 5.4 AIME, harder Prove it Bulgaria

Let $n \in \mathbb{N}$ and $\mathcal{A}$ be a nonempty family of nonempty subsets of $\{1, 2, \dots, n\}$ with the following property – if $A \in \mathcal{A}$ and $A \subset B \subseteq \{1, 2, \dots, n\}$ , then $B \in \mathcal{A}$ . Prove that the function
$f(x) := \sum_{A \in \mathcal{A}} x^{|A|} (1-x)^{n-|A|}$
is strictly increasing in the interval $(0, 1)$ .

Solution

Let $0 < p < q < 1$ . Notice that $p^* = \frac{q-p}{1-p} \in (0, 1)$ . We construct the sets $X$ and $Y$ as follows: For each element $i \in \{1, 2, \dots, n\}$ we put $i$ in $X$ with probability $p$ (independently of each other), and for each element $j \in \{1, 2, \dots, n\} \setminus X$ we put $j$ in $Y$ with probability $p^*$ . Then $P(x \in X \cup Y) = p + (1-p)p^* = q$ . It is easy to see that $f(p) = P(X \in \mathcal{A})$ , and $f(q) = P(X \cup Y \in \mathcal{A})$ , but since $\mathcal{A}$ has the property from the condition we have that $X \subseteq X \cup Y \Rightarrow f(p) < f(q)$ .
$\square$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.