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.”