| |||||||||||||

## IMC2021: Day 1, Problem 2
Prove that the probability \(\displaystyle \mathsf{P}\Big(\min(Y)>\max(X)\Big) \) does not depend on \(\displaystyle a\). Fedor Petrov, St. Petersburg State University
The number of such choices with \(\displaystyle \min(Y)>\max(X)\) is equal to \(\displaystyle \binom{n+k+a}{n+k}\) since this is the number of choices for the \(\displaystyle n+k\)-element set \(\displaystyle X \cup Y\) and this union together with the condition \(\displaystyle \min(Y)>\max(X)\) determines \(\displaystyle X\) and \(\displaystyle Y\) uniquely. Hence the probability is \(\displaystyle \frac{\binom{n+k+a}{n+k}}{\binom{k+a}{k} \cdot \binom{n+k+a}{n}}=\frac{1}{\binom{n+k}{k}} \) where the identity can be seen by expanding the binomial coefficients on both sides into factorials and canceling. Since the right hand side is independent of \(\displaystyle a\), the claim follows.
Note that \(\displaystyle \{Z_n:=Y,Z_k:=f(X),Z_a:=f(\{1,2,\dots,k+a\}\setminus X)\} \) is a random partition of \(\displaystyle \{1,\ldots,n+k+a\}=Z_n\sqcup Z_k\sqcup Z_a \) into an \(\displaystyle n\)-subset, \(\displaystyle k\)-subset, and \(\displaystyle a\)-subset. If an \(\displaystyle a\)-subset \(\displaystyle Z_a\) is fixed, the conditional probability that \(\displaystyle \min(Z_k)>\max(Z_n)\) always equals \(\displaystyle 1/\binom{n+k}k\). Therefore the total probability also equals \(\displaystyle 1/\binom{n+k}k\). | |||||||||||||

© IMC |