Probability brainteaser

Normal 52 card deck. Cards are dealt one-by-one. You get to say when to stop. After you say stop you win a dollar if the next card is red, lose a dollar if the next is black. Assuming you use the optimal stopping strategy, how much would you be willing to pay to play? Proof?

If there are $r$ red cards on a total of $n$ cards let $p(r,n)$ be the probability to win with the optimal strategy. If you stop immediately you win with probability $r/n$. If you don't stop you can get a red card with probability $r/n$ and then you win with probability $p(r-1,n-1)$. If instead you get a black card you win with probability $p(r,n-1)$. Hence with the best strategy you win with probability $$p(r,n) = \max\left\{\frac r n, \frac r n p(r-1,n-1) + \frac{n-r} n p(r,n-1)\right\}.$$ Let's prove by induction that $p(r,n)=r/n$. Suppose it is true for $n-1$ that $p(r,n-1)=r/(n-1)$ then $$p(r,n) = \max\left\{\frac r n, \frac r n \frac{r-1}{n-1}+\frac{n-r}n\frac{r}{n-1} \right\} = \max\left\{\frac r n, \frac{nr-r}{n(n-1)}\right\} = \frac r n.$$ In the case $n=1$ you immediately find that $p(0,1)=0$ and $p(1,1)=1$.

So at anytime you stop you always get the same probability to win. If you start with the same number of red and black cards, you win with probability $1/2$ hence you should pay nothing to play.

• Or to stop after the second card. Or the third card. Or... – TonyK Jul 6 '13 at 22:50
• Your analysis shows the expectation is zero. Why are you willing to pay 2 dollars (or for that matter, any fee) to play? Am I missing something? – soakley Jul 12 '13 at 3:15
• The expectation is to win with 50% probability. If you win a dollar to have expectation 0 you whould pay two dollars. – Emanuele Paolini Jul 13 '13 at 7:34
• @EmanuelePaolini Why would you ever pay two dollars to play a game where you can only win one dollar? In this game you will either lose one or three dollars, if you pay two to play. – Gibarian Jul 16 '13 at 15:48
• @Gibarian, soakley: you are right i didn't read carefully the statement. – Emanuele Paolini Jul 16 '13 at 20:14

The quick solution is: you may just bet on the color of the last card, not the next one. The game is not changed as you have the same info about next and last cards. So any strategy in original game is optimal :)

The teaser is mentioned in Peter Winkler's Games people don't play.