You are currently browsing the monthly archive for August 2010.

Suppose you have a set of cards labeled 1, 2, …, N. You shuffle them, and start dealing out the deck. As you deal it out, you keep a card if it’s the highest card you’ve seen so far. Otherwise you discard it.

You always end up keeping the first card; you keep the second only if its higher than the first, the third only if its higher than both of the previous two, etc.

On average, how many cards do you keep once you’ve dealt through the entire pack?

A related problem to the last post. You toss a fair coin, and keep going until the number of tails you’ve seen is n more than the number of heads. On average, how many times do you toss the coin before you stop?

Unlike the last problem, I don’t know the answer to this one, so I’d be interested in hearing anyone else’s approach. I believe that I have a good method for getting at the answer, but that I’m missing one crucial step that I haven’t yet been able to fill in.