2
$\begingroup$

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.

$\endgroup$
2

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Your induction proves that no strategy can have a better than $26/52$ chance of winning. So if you can show that the strategy "take the top card" has a $26/52$ chance of winning, then you have shown that no strategy can do better than "take the top card". This is not hard to establish, by a similar induction argument.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .