Library / /15 of 28

, 2024

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

Mark has a cursed six-sided die that never rolls the same number twice in a row, and all other outcomes are equally likely. Compute the expected number of rolls it takes for Mark to roll every number at least once.

Solution

Solution:

Suppose Mark has already rolled $n$ unique numbers, where $1 \leq n \leq 5$ . On the next roll, there are $5$ possible numbers he could get, with $6-n$ of them being new. Therefore, the probability of getting another unique number is $\frac{6-n}{5}$ , so the expected number of rolls before getting another unique number is $\frac{5}{6-n}$ . Since it always takes $1$ roll to get the first number, the expected total number of rolls
is $1+\frac{5}{5}+\frac{5}{4}+\frac{5}{3}+\frac{5}{2}+\frac{5}{1}=\frac{149}{12}$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.