Wednesday, February 5, 2014

Betting on cards

A deck consisting of $n$ red cards and $n$ black cards are shuffled. The cards are then flipped one at a time. Before each flip, you are allowed to make a bet on the color of the next card. If you guessed right, you win an amount equals to your bet. If you guessed wrong, you lose your bet. You don't have to bet on every flip, in fact you don't have to bet at all if you so wish. The bets can be any amount of real number, and you start with one dollar.

You decide to employ the following strategy. Suppose that, by counting already-flipped cards, you deduce that there are $R$ red cards and $B$ black cards left in the deck. If $R > B$, you guess red while betting $\frac{R-B}{R+B}$ of your total money. Similarly if $R < B$ you guess black while betting $\frac{B-R}{B+R}$ of your total money. If $R=B$ you don't bet that turn. Show that this strategy guarantees a final amount of: $$\frac{2^{2n}n!n!}{(2n)!}$$ Note: this final amount is much bigger than people think. That sum equals to: $$\left(1 + \frac{1}{2n-1} \right) \left(1 + \frac{1}{2n-3} \right) \dots \left(1 + \frac{1}{3} \right) \left(1 + \frac{1}{1} \right)$$ which is already greater than 2, and only increases as $n$ increases. This is an extension to the obvious strategy to wait until the last card before we bet the one dollar that we start with, to which we'd be guaranteed a final amount of two.

First Solution

First we claim the following: if at any point there are $R$ red cards and $B$ black cards left in the deck, and your current total is $x$, employing the above strategy will give you a final amount of: $$\frac{2^{R+B}R!B!}{(R+B)!} x$$ That claim is easily verified if either $R+B=1$ because then we would know exactly what's left in the deck. Now we prove the claim by induction on $R+B$. Clearly if $R=B$ then we don't bet that flip, and we reduced it to the case $R+B-1$. But if $R \neq B$, and WLOG we may assume that $R > B$. We bet $\frac{R-B}{W+B}$ that the next card will be red.

Case 1: the next card is red. That means our current total becomes $(1 + \frac{R-B}{R+B})x = \frac{2R}{R+B}x$. But the deck now contains $R-1$ red and $B$ black, so by our induction hypothesis, our final amount will be: $$\frac{2^{R+B-1}(R-1)!B!}{(R+B-1)!} \frac{2R}{R+B}x =\frac{2^{R+B}R!B!}{(R+B)!} x $$

Case 2: the next card is black and we lost our bet. That means our current total is now $(1 - \frac{R-B}{R+B})x = \frac{2B}{R+B}x$ and the deck contains $R$ red and $B-1$ black, so our final amount is: $$\frac{2^{R+B-1}R!(B-1)!}{(R+B-1)!} \frac{2B}{R+B}x =\frac{2^{R+B}R!B!}{(R+B)!} x $$ And the claim is proven. Now it's straightforward to apply that if $R=B=n$, we have: $$\frac{2^{2n}n!n!}{(2n)!} = \frac{(2n)(2n-2)\dots (4)(2)}{(2n-1)(2n-3) \dots (3) (1)}$$ $$= \left(1 + \frac{1}{2n-1} \right) \left(1 + \frac{1}{2n-3} \right) \dots \left(1 + \frac{1}{3} \right) \left(1 + \frac{1}{1} \right)$$

No comments:

Post a Comment