## Problem of the Day #395: DessertApril 17, 2012

Posted by Saketh in : potd , trackback

Alex just had a sumptuous dinner at his favorite restaurant. He now has $n$ different choices for dessert.

With so many good options, he decides to pick randomly using a coin. However, he wants to ensure that each dessert has an equal probability of being picked.

Devise a strategy for choosing dessert that minimizes the expected number of flips needed, and express the expected number in terms of $n$.

Bonus: Now solve the same problem in the case that Alex’s coin is weighted to land heads more often than tails.