At a restaurant, how can Jack choose one out of three desserts with equal probability with the help of a coin? What if the coin is biased and the bias is unknown?

A simple problem commonly encountered in introductory classes on randomized algorithms.

Toss the coin twice. Let TH, HT and TT correspond to the three choices. If HH, repeat. This takes 8/3 tosses on average. If the coin were biased, TH and HT would occur with equal probabilty. So one strategy could be to assign THHT, HTTH and THTH to the three choices, with other 4-toss outcomes rejected. An alternative strategy is to assign HTT, THT and HTT to the three choices, with other 3-toss outcomes rejected.