International Mathematics Competition
for University Students
2021

IMC2021: Day 1, Problem 2

Problem 2. Let \(\displaystyle n\) and \(\displaystyle k\) be fixed positive integers, and let \(\displaystyle a\) be an arbitrary non-negative integer. Choose a random \(\displaystyle k\)-element subset \(\displaystyle X\) of \(\displaystyle \{1,2,\ldots,k+a\}\) uniformly (i.e., all \(\displaystyle k\)-element subsets are chosen with the same probability) and, independently of \(\displaystyle X\), choose a random \(\displaystyle n\)-element subset \(\displaystyle Y\) of \(\displaystyle \{1,\ldots,k+n+a\}\) uniformly.

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

Solution 1. The number of choices for \(\displaystyle (X,Y)\) is \(\displaystyle \binom{k+a}{k} \cdot \binom{n+k+a}{n}\).

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.

Solution 2. Let \(\displaystyle f\) be the increasing bijection from \(\displaystyle \{1,2,\dots,k+a\}\) to \(\displaystyle \{1,\ldots,k+a+n\}\setminus Y\). Note that \(\displaystyle \min(Y)>\max(X)\) if and only if \(\displaystyle \min(Y)>\max(f(X))\).

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\).