We play a game with a randomly shuffled deck of $52$ regular playing cards. Cards are placed
face down on table. You have two options, either “take” or “skip” the top card. The skipped card is
revealed and game is continued. If only one card is left in deck it is automatically taken. Game stops
when you take the top card; you win if the card taken is black, otherwise you lose.
Prove that no other strategy is better than taking the top card.
I was able to get up to this point
Every strategy has probability $26/52$ of winning (assuming $26$ red and $26$ black cards). To show this we will use induction to prove the stronger result that for an $n$ card , $x$ of whose cards are of black color, and $y$ cards are non-black, the probability of winning is $\frac x{x+ y}=x/n$, no matter what strategy is employed. Since this is clearly true for $n=1$, assume it to be true for an $n-1$ card deck , and now consider an $n$ card deck. Fix any strategy, and let $p$ denote the probability that strategy guesses that card to be flipped is of black color. Given that it does, the player’s probability of winning is $x/n$. If, however the strategy does not guess that the flipped card is of black color, then the probability that that player wins is the probability that the first $x$ cards are not of black color, namely, $n-x/n$, multiplied by the conditional probability of winning given that the first $x$ cards are not of black color. But this later conditional probability is equal to probability of winning when using an $n-1$ card deck containing $x$ black cards; it is thus by induction hypothesis $\frac x{n-1}$. Hence, given that the strategy does not guess the first $x$ cards, the probability of winning is $\frac{n-1}n\cdot\frac x{n-1}=x/n$.
Thus letting $G$ be event that the first card is flipped with black color on it, we obtain
$$\Bbb P(\text{win}) = \Bbb P(\text{win}|G)\Bbb P(G) + \Bbb P(\text{win}|G_c)(1-\Bbb P(G))=\frac{px}n+\frac{x(1-p)}n = x/n$$
But I am not able to prove that better strategy is taking the top card? Please help.
Best Answer
You have proved it. You showed that every strategy has probability $\frac{x}{x+y}$ of winning, and so all strategies are optimal, and so picking the top card is optimal.
Alternatively, you can just make your induction hypothesis that in any deck, taking the top card is optimal. Then in your inductive step, you will either take the top card, or take the second top card, and clearly both are optimal.