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?

Advertisements