Expected number of steps to finish all the cookies

Solution 1:

Let's consider the general case with $2^s$ cookies, labelled with subsets of $\{1,2,\ldots,s\}$. Steve begins by choosing a random ordering of all the cookies. At each step, Steve eats the next available cookie, and instead of eating the remaining cookies whose label is a subset, let's say he simply discards them. The number of steps is equal to the total number of cookies eaten.

A particular cookie will eventually be eaten if and only if that cookie is first among those cookies whose labels are supersets of that cookie's label. If the label on a cookie has size $k$, there are $2^{s-k}$ possible supersets, so the probability that cookie gets eaten is $2^{k-s}$. There are ${s\choose k}$ cookies whose label has length $k$, so by linearity of expectation, the expected number of steps (= cookies eaten) is $$ \sum_{k=0}^s {s\choose k}2^{k-s}=\left(\frac{3}{2}\right)^s. $$

Solution 2:

All you care about is when he eats the $\{1,2,3,4,5,6,7,8\}$ cookie. If he chooses it he is done, and no other combination of cookies will cause him to eat it. He chooses cookies until he chooses $\{1,2,3,4,5,6,7,8\}$, which is uniform on $[1,256]$ with expected value $\frac {257}2$

Added: as alex.jordan points out, this is not correct. If he doesn't choose the empty set cookie first, it gets eaten in the first batch and will never get chosen. This reduces the number of choices before $\{1,2,3,4,5,6,7,8\}$ gets chosen.