I had some help solving the Riddler Classic this week from my friends Tom and Al at work. I also enjoyed Tom's paraphrasing of the puzzle:

You want to play a board game, but you don't have a die. You go to the magical coin store that will sell you a single coin with whatever weighting you want. Find the smallest $k$ coin flips whose sequences can be partitioned to correspond to die faces with equal probability.

Initial thoughts

The basic setup is that you want to find the smallest value of $k$ where you can choose a $p = P(H)$ such that every sequence of $k$ coin flips belongs to exactly one (six-sided, fair) die face value, and that each die face value's sequences sum to equal probability, namely, $1/6$. It is clear that the sequences need not be of equal length.

Solution

The crucial thing to notice is that you have to do lots of binomial expansions of the type $$ p^n(1-p){n-1} $$ and it's easy to overlook that $$ (1-p)^{n-1} $$ is also a binomial expansion. In fact, if we consider \begin{align} p^n(1-p)n-1 & = p^n + (1-p)^n \end{align}