There are n cards on a table numbered from $1$ to $n$, where $n$ is an even number. Two people take turns taking away the cards. The first player will always take the card with the largest number on it, but the second player will take a random card. Prove: the probability that the first player takes the card with the number $i$ is $ \frac{i-1}{n-1} $
Problem
Source: 2021 IMOC qualification problem, C3
Tags: IMOC, combinatorics
31.12.2021 17:08
Denote by $R(n,j)$ the probability in question. After the first round (i.e. both players have made one move), we are again in a similar situation and the first player is about to make his move, but this time, the cards are $n-2$. This is a motivation to use a recurrence relation approach. So, when $j=n$, obviously $R(n,n)=1.$ Let $1\le j\le n-1$. The first player takes card number $n$ and the second player has three options: \begin{align*} &1) \text{ takes a card \# } \ell \text{ where } j+1\le \ell\le n-1; \\ &2) \text{ takes a card \# }\ell \text{ where }1\le \ell \le j-1;\\ &3) \text{ takes the card \# } j. \end{align*}In the third case the winner is the second player, so there are two opportunities in order the first player to win (to take the $j$-th card). Thus, we can write the relation $$R(n,j)=\frac{n-1-j}{n-1}R(n-2,j)+ \frac{j-1}{n-1}R(n-2,j-1)\qquad(1)$$Indeed $\frac{n-1-j}{n-1}$ is the probability the first case to happen, and after that we are in position we have $n-2$ cards ordered in increasing order and the first player should take the $j$-th one. The second case is similar. Having in mind $(1)$ it's easy to finish the job. Indeed, for $n=2$ it holds $R(2,j)=\frac{j-1}{2-1}$. So, if it's true for $n-2$, putting it in $(1)$ and making an easy calculation, we get $R(n,j)=\frac{j-1}{n-1}$.