IMC 2021 · Day 1 · P2

Hint: The sets $X$ and $Y$ with $\min(Y) > \max(X)$ are uniquely determined by $X \cup Y$.

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

The number of such choices with $\min(Y) > \max(X)$ is equal to $\binom{n+k+a}{n+k}$ since this is the number of choices for the $(n+k)$-element set $X \cup Y$ and this union together with the condition $\min(Y) > \max(X)$ determines $X$ and $Y$ uniquely (note in particular that no elements of $X$ will be larger than $k + a$).

Hence the probability is $$\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 $a$, the claim follows.

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

Note that $$\{ Z_n := Y, \ Z_k := f(X), \ Z_a := f(\{1, 2, \dots, k+a\} \setminus X) \}$$ is a random partition of $$\{1, \dots, n+k+a\} = Z_n \sqcup Z_k \sqcup Z_a$$ into an $n$-subset, $k$-subset, and $a$-subset.

If an $a$-subset $Z_a$ is fixed, the conditional probability that $\min(Z_k) > \max(Z_n)$

always equals $1 / \binom{n+k}{k}$. Therefore the total probability also equals $1 / \binom{n+k}{k}$.