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

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

  Solution