Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns

**0**OR

**1**both with a probability of

**1/2**, how can we implement a function that returns integers from

**a**to

**b**(

**b**>

**a**), all with a probability of

**1/n**, where

**n = (b-a+1)**

Source : Cormen - Problem 5.1-2 (randomized algorithms)

Similar problem :

At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin?

Its on Gurmeet's site here http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-tossing-with-one-third-probability/