Track / Stage 4 / 316 of 340 #576 of 2000

Problem 576

AMC 12 late, AIME early

Combinatorics Difficulty 5.0 Prove it 10th Annual Harvard-MIT Mathematics Tournament · United States

Problem:

Forty two cards are labeled with the natural numbers $1$ through $42$ and randomly shuffled into a stack. One by one, cards are taken off of the top of the stack until a card labeled with a prime number is removed. How many cards are removed on average?

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

Solution:

Answer: $\frac{43}{14}$ . Note that there are $13$ prime numbers amongst the cards. We may view these as separating the remaining $29$ cards into $14$ groups of nonprimes - those appearing before the first prime, between the first and second, etc. Each of these groups is equally likely to appear first, so $29/14$ nonprimes are removed on average. We are done since exactly one prime is always drawn.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.