# International Mathematics Competition for University Students 2021

Select Year:

IMC 2021
 Information Schedule Problems & Solutions Results Contact

## 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$. IMC1994 IMC1995 IMC1996 IMC1997 IMC1998 IMC1999 IMC2000 IMC2001 IMC2002 IMC2003 IMC2004 IMC2005 IMC2006 IMC2007 IMC2008 IMC2009 IMC2010 IMC2011 IMC2012 IMC2013 IMC2014 IMC2015 IMC2016 IMC2017 IMC2018 IMC2019 IMC2020 IMC 2021 