Olympiad Maths Prep

Library / /4 of 4

Combinatorics Difficulty 5.4 AIME, harder Prove it Bulgaria

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

Solution

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

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.