3
$\begingroup$

You have a deck of cards, 26 red, 26 black. These are turned over, and at any point you may stop and exclaim "The next card is red.". If the next card is red you win £10.

What's the optimal strategy? Prove this is the optimal strategy.

I feel like the optimal strategy is whenever you are in a state that you flip more black than red cards you call out red card, but I do not know how to prove it, nor can I think of why it must be the absolute best strategy.

Thanks for any help.

  • 0
    I have replaced [brainteaser] by [puzzle], but I'm not sure either is needed.2012-06-16

2 Answers 2

7

There is no optimal strategy (or rather, every strategy is optimal). Assuming your strategy involves exclaiming before the last card is drawn, your expected winnings are 5 pounds.

If you don't exclaim, your winnings are obviously zero.

Here's a reference: "Games People Don't Play" (Peter Winkler)

  • 0
    This is a really fun paper. Thanks!2012-06-17
3

We deal first with deterministic strategies, adding the obvious rule that a call must be made on or before the $52$nd card.

The first step is an existence proof: there are optimal deterministic strategies. For among the finitely many deterministic strategies, there must exist one or more that maximizes expectation.

Suppose that Alice chooses an optimal strategy, and plays it for red, and independently Bob chooses and plays an optimal strategy for black. Let random variable $X$ denote Alice's winnings, and let $Y$ denote Bob's winnings. (The sample space is the set of permutations of the cards, assumed all equally likely.)

Then $E(X+Y)=10$. So by linearity of expectation, $E(X)+E(Y)=10$, and by symmetry $E(X)=E(Y)$, so $E(X)=5$.

Suppose that under the same conditions, we selflessly try to minimize the expected return. The above argument shows that again the expectation is $5$. So all deterministic "strategies" lead to the same expected return.

Now we briefly consider probabilistic strategies, for which the probability of what one does next (call or not call) is a function of the sequence of cards already seen, but nothing else. It is not hard to show that again in this case there are optimal strategies, and the rest of the argument is the same.

There may be more general notions of strategy. The above arguments are silent about these.