I seem to have accumulated a backlog of subject matter that I have found interesting recently.  I’ll get back to it soon… but right now, in the spirit of not getting back to work just yet, following is another puzzle involving a card game.  I found this problem in Peter Winkler’s Mathematical Puzzles: A Connoisseur’s Collection.  This is an excellent book, with more than just the “same old” problems, but also including some interesting twists that were new to me.

For example, recall the card puzzle motivating the discussion of other players’ strategy (not) affecting your expected return in blackjack.  Winkler discusses this problem, but only as a prelude to the following more challenging variant:

Problem: Consider a standard, shuffled poker deck of 52 playing cards, of which 26 are red and 26 are black.  You start with one dollar.  For each of 52 turns, I will deal one card at a time face up on the table between us.  At each turn, you may bet any fraction of your current bankroll (from “passing” to betting everything you have) on the color of the next card to be dealt, paying even odds if your guess is correct.  For example, a conservative strategy would be to wait until the last card, whose color you will know with certainty, and bet your whole dollar, guaranteeing a net return of one dollar.

Can you do better than this?  Like the earlier problem, it is interesting to consider maximizing both the expected (i.e., average) return, as well as the worst case return.  And also like the earlier problem, this is a great combination of “write a short program to compute optimal strategy” and “use pencil and paper to show why the program’s output makes sense.”

Let’s play the following simple game: I will shuffle a standard 52-card deck, and deal one card at a time face up onto the table between us.  You can say “Stop” at any time, at which point I will pay you an amount equal to the fraction of cards dealt so far that are red.  For example, if you stop after seeing a single card, you win 1 if it is red, 0 if it is black, with expected return 1/2.  Of course, you can wait until the entire deck is dealt, also with a guaranteed return of 1/2.

The problem is: can you do better than this?  What is the optimal strategy for playing this game, and what is the corresponding expected return?

(This game is a variant of the following interesting game that I read about this week, which at first glance might seem even simpler, but for which optimal strategy remains an open problem: instead of dealing cards from a deck, I flip a coin repeatedly, and upon stopping I pay you an amount equal to the fraction of tosses that came up heads.)