## Problem of the Day #208: Binary CoinsOctober 13, 2011

Posted by Alex in : potd , trackback

Saketh wants to purchase some food worth a random value of cents between $0$ and $1,000,000$, inclusive. He has coins worth $1$ cent, $2$ cents, $4$ cents, and so on to infinite powers of $2$, with an infinite number of coins for each value. What is the expected number of coins that Saketh will use to purchase his food, given that he always uses the fewest possible number of coins?