At a restaurant, how can Veronica 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?

Source

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

Solution

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.

30 coins of arbitrary denominations are laid out in a row. Simran and Tavleen alternately pick one of the two coins at the ends of the row so as to pick up as much money as possible. If Simran makes the first move, could Tavleen ever collect more money than Simran, if Simran makes the optimal choices?