Great Expectations. Topic: Probability. Level: AMC/AIME.

Definition: The expected value of a random variable $ X $ is $ \displaystyle \sum_x x \cdot p(x) $, where the summation is taken over all possible values $ x $ of $ X $ and $ p(x) $ is the probability that $ X = x $. For example, the expected value of a die roll is

$ 1 \cdot \frac{1}{6}+ 2\cdot \frac{1}{6}+ \cdots + 6 \cdot \frac{1}{6} = \frac{7}{2} $.

--------------------

Problem: What is the expected number of rolls on a standard die that you need to make before every number shows up at least once?

Solution: Let $ E_n $ be the expected number of rolls before $ n $ of the numbers shows up at least once. Clearly, $ E_1 = 1 $. Then

$ E_2 = \frac{5}{6}(E_1+1)+\frac{1}{6}(E_2+1) $

because there is a $ \frac{5}{6} $ probability that it will take exactly one more than $ E_1 $ (if we roll a new number) and a $ \frac{1}{6} $ probability that it will result in the same number as before and we start from the same situation again. Using this same argument, we deduce that

$ E_{n+1} = \frac{6-n}{6}(E_n+1)+\frac{n}{6}(E_{n+1}+1) $,

which is equivalent to

$ E_{n+1} = E_n+\frac{6}{6-n} $.

Since we want to find $ E_6 $, we just apply this recursion $ 6 $ times to get

$ E_6 = 6\left(1+\frac{1}{2}+\cdots+\frac{1}{6}\right) = 14.7 $.

QED.

--------------------

Comment: Expected value is an interesting topic and can result in a bunch of strange recursions, but it's quite cool in that respect. It's "possible" to solve this problem using only probability, but that would get very ugly very quickly.

--------------------

Practice Problem: Generalize this to a die with $ 8 $, $ 12 $, or $ 20 $ sides (the three bigger regular die which exist).