Tossing with One-Third Probability
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?
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.
Three out of six lookalike balls are heavy. The other three are light. How many weighings on a beam balance are necessary to identify the heavy balls?
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?
12 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.