Track / Stage 6 / 114 of 400 #1114 of 2000

Problem 1114

National olympiad, first round

Combinatorics Difficulty 6.2 Prove it

7・16 A deck of cards has $N$ cards, among which there are three $A$ s. Now, the deck is shuffled randomly (assuming all possible distributions of the cards have an equal chance), and then the cards are flipped one by one from the top until the second $A$ appears. Prove that the expected (average) number of cards flipped is $\frac{N+1}{2}$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

[Proof] Let $x_{1}, x_{2}, x_{3}$ represent the positions of the three Aces in any given deal, i.e., the three Aces are the $x_{1}$ -th, $x_{2}$ -th, and $x_{3}$ -th cards.

Then in the reverse deal, i.e., dealing from the last card, the position of the second Ace in the sequence is
$x_{2}^{\prime}=N+1-x_{2} \text {. }$

Thus, regardless of whether $N$ is odd or even, the average position is
$\frac{x_{2}+\left(N+1-x_{2}\right)}{2}=\frac{N+1}{2} \text {. }$

Clearly, this is the expected number of cards turned over.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.