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

3 Answers 3

Reset to default
2
$\begingroup$

There is a much simpler solution:

Consider the similar game where instead of taking the next card, you take the last card in the deck. Then indeed this game is identical to before, since any strategy that would work in the former would work in the latter, since it must treat the cards remaining in the deck identically. But the probability of this card being black is $\frac{1}{2}$, irrespective of what cards you see, since the card is fixed once the deck is shuffled. Hence, you cannot beat $\frac{1}{2}$.

$\endgroup$
7
  • $\begingroup$ I kind of get it but isn't the probability of the last card being black $P(B|S)$ (i.e. the probability that the last card is black given that we have seen $r$ red cards and $b$ black according to our strategy) the right probability to use. Whereas $\frac{1}{2}$ is the probability of the last card is black before we observed any cards. $\endgroup$
    – Apex345
    Commented Aug 9 at 14:02
  • $\begingroup$ @Apex345 The strategy starts off when we have an equal number of black and red cards. Hence, the probability of the last card being black is $\frac{1}{2}$, and so any strategy you come up with from the start will at best have a performance of $\frac{1}{2}$. $\endgroup$
    – Sharky Kesa
    Commented Aug 9 at 14:31
  • $\begingroup$ @Apex345 Now, if you decide to just reveal a few cards until you know there $r$ red cards, and $b$ black cards in the deck, then the probability of winning is now $\frac{b}{r + b}$, but you are equally likely to get into this position as you are to get into a position with $b$ red cards and $r$ black cards, so by symmetry no strategy will be beating $\frac{1}{2}$ at the start. $\endgroup$
    – Sharky Kesa
    Commented Aug 9 at 14:32
  • $\begingroup$ Thanks for the reply. I get that the prob of getting to $r$ red and $b$ black cards is the same as the probability of getting $b$ red and $r$ black cards. Maybe this is obvious, but how do we conclude from this that no strategy can beat $\frac{1}{2}$ at the start? For example, what happens if our strategy was as follows - 'pick cards until your probability of winning is more than $p$ where $1\ge p \ge \frac{1}{2}$, otherwise pick the last card'. $\endgroup$
    – Apex345
    Commented Aug 10 at 9:48
  • $\begingroup$ In this case, I get that by symmetry, the probability of getting to a position where your prob of winning is $\ge p$, is the same as the prob that you get in a position where your probability of winning is less than $1-p$, but aren't we interested in the probability that you don't get in that position instead? $\endgroup$
    – Apex345
    Commented Aug 10 at 9:48
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$

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