Chapter 4, Problem 4.16P

A deck of n cards numbered 1 through n are to be turned over one a time. Before each card is shown you are to guess which card it will be. After making your guess, you are told whether or not your guess is correct but not which card was turned over. It turns out that the strategy that maximizes the expected number of correct guesses fixes a permutation of the n cards, say 1, 2,. . ., n, and then continually guesses 1 until it is correct, then continually guesses 2 until either it is correct or all cards have been turned over, and then continuality guesses 3, and so on. Let G denote the number of correct guesses yielded by this strategy. Determine $P\left(G=k\right)$

Hint: In order for C to be at least k what must be the order of cards 1,…,k.