You have $100 to bet on the following game: take a shuffled deck of cards, and deal through it one at a time.

Let G(r,b) be the minimum guaranteed amount by which an initial stake
is multiplied, following best strategy, with r red and b black cards
remaining.  The problem asks for G(26,26)*$100.

For r>=b, assume we bet a percentage X(r,b) of our current stake that a
red card is dealt.  Then if we win (i.e., a red card is dealt), we will
be guaranteed (1+X(r,b))*G(r-1,b).   If we lose, we will be guaranteed
(1-X(r,b))*G(r,b-1).  Select X(r,b) so these two are equal.  This gives

     X(r,b)=(G(r,b-1)-G(r-1,b))/(G(r,b-1)+G(r-1,b))
and
     G(r,b)=2*G(r,b-1)*G(r-1,b)/(G(r,b-1)+G(r-1,b)).   (**)

If r<b, we bet X(r,b) on a black card and arrive at the same recursive
equation for G(r,b).  So for general r,b we equation (**) holds, and

     X(r,b)=|G(r,b-1)-G(r-1,b)|/(G(r,b-1)+G(r-1,b))

Note that G(r,b) must be symmetric, so X(r,r)=0.  That is, we should
bet zero when equal numbers of red and black cards remain, such as on
the first deal.  The amount we should bet gets larger as r and b get
farther apart.

Equation (**) can be solved recursively to give the desired G(26,26).
To start the recursion, we have for all r and b,

     G(r,0)=2^r   and   G(0,b)=2^b.

I couldn't derive a closed form solution for G, but a simple
spreadsheet calculation shows that

    G(26,26)=9.08132955;  i.e., your $100 turns into $908.13.

Note:  This strategy not only guarantees the minimum win, but assures
that the final win will be exactly equal to G(26,26).  So the maximum
win equals the minimum win equals the expected win.

-- Ken Smith <ken@jpl354.jpl.nasa.gov>

This answer is correct.  On each card, you bet an amount equal to (2p-1),
where p is your probability of winning the bet.
I.e. p = R/(R+B) if there are more red than black cards.
This is also the ratio you would bet to maximize the expected log
of your bankroll.

The strategy and resulting gain is easy to demonstrate by enumeration
for small decks.

Ken Smith has given a solution by recursion.  An alternate proof is:

Consider a new game where you place bets on the entire shuffle.
There is a great big solar system-sized betting layout with
all possible sequences of red and black, and you are required
to divide your entire bankroll among these bets, which all
pay $2^52 for a $1 bet.  With no "house take" this is completely
general, because you may make offsetting bets to simulate
betting only part of your capital.  With a little thought, it
can be seen that this is exactly equivalent to the original game.

If the deck is sampled with replacement, your optimal strategy
is to bet 2^-52 of your bankroll on each space.  Only one deck
will occur, and that bet will return your original bankroll.

In this case, however, the deck is sampled without replacement,
so we know that a large number of configurations can not occur.
Reapportion your bets to place an equal amount on each of the
decks which represent possible shuffles.  Each bet is 1/C(52,26).
One of these will win, returning

2^52 / C(52,26) = 9.0813 of your original bankroll, = $908.13

This analysis can also be used to find the optimal bet.  With N cards
remaining, R of them red, we have made a total of C(N,R) bets
on configurations like this.  C(N-1,R-1) of them are betting on
the next card being red.

So we bet C(N-1,R-1)/C(N,R) = R/N of our current bankroll on red,
and (N-R)/N on black.  Canceling the offsetting bets, we have bet
2(R/N)-1 on red (assuming there are more red cards) or 2p-1 as
stated above.

-- James Layland <jlayland@grissom.jpl.nasa.gov>

The answer to this has already been posted, as well as a nice argument
for it, but I have a moderately rigorous proof.

The answer, once again, is that when there are R red cards and B black
cards remaining, and there are more red cards than black, you bet
(R - B)/(R + B) times the amount of money you currently have (your
capital) that the next card will be red.  An alternative way to say
this is you bet 2p - 1 times your capital, where p is the computed
probability that the next card is red.  There's a similar rule but
with red/black interchanged when there are more black cards than red.
You will then end up with

  2^52/C(52,26) * 100  = (52/51)(50/49)...(4/3)(2/1) * 100

dollars.

............................

In general, S is a "strategy for deck(R,B) with initial capital C" if
S is a set of rules that tells you how to bet on each card that is
dealt from a deck of R red and B black cards when you start out with C
dollars, depending on what cards have been dealt so far in what order
(these determine what cards remain in the deck and also what your
current capital is).  This is a broader class of strategies than we
will turn out to need, but we want the class of strategies to
encompass all variables so we're sure we didn't leave out the optimal
strategy.

It's not too hard to see that you can completely specify a strategy S
just by specifying the portion of your current capital to bet on which
color at each point, since the cards already dealt determine your
current capital.  But I won't actually show this rigorously.  If S is
defined in this way, we say simply that it is a "strategy for
deck(R,B)," which can be applied to any initial capital.  Then
every outcome is simply proportional to the initial capital.

If S is a strategy for deck(R,B), there are only C(R + B,R) possible
outcomes (corresponding to different deals of the deck) when you play
S with some initial capital.  Let guarantee(S) be the worst such
outcome when the initial capital is 1, i.e., the multiplier by which S
can guarantee to increase your capital.  Clearly, guarantee(S) is
bounded by 2^(R + B), but take the least upper bound over all possible
strategies S, and call this f(R,B).  So f(R,B) is the maximum you
could end up with starting with 1 dollar (and we have not yet decided
whether you can achieve f(R,B) exactly or merely get arbitrarily close
to it).  Again, it's not hard to see that if you start with C dollars,
the maximum you can end up with is C*f(R,B).

Theorem:  For all R >= 0 and B >= 0,
~~~~~~~

   f(R,B) = (2^(R + B)) / C(R + B,R).

Moreoever, there is a strategy that achieves this maximum.

Proof: By induction on R + B.  For all R and B such that R + B = 0,
there are no bets to be made, so f(R,B) = 1 and this maximum is
achieved by some strategy (in fact, by any strategy).  This satisfies
the base case.

Inductive step: Suppose that for all R and B such that R + B = n, for
some n >= 0, it is true that f(R,B) = (2^(R + B))/C(R + B,R) and there
is a strategy S{R,B} that achieves this maximum.  Now take any R and B
such that R + B = n + 1.  If R = 0, the best you can do is bet all
your money on black for every card that is dealt; you will win every
time and double your money B times, so 2^B = (2^(R + B))/C(R + B,R) is
the value of f(R,B) and the value is achieved by this strategy.  We
get a similar result for B = 0.

But suppose R > 0 and B > 0 and you have 1 dollar capital.  At this
point you bet some amount r that the next card is red, where
-1 <= r <= 1.  (A bet with r < 0 is actually a bet of -r that the next
card is black.)  If the next card is red, you get to play with R - 1
red cards, B black cards, and starting capital of 1 + r, so the best
you can do from that point is

  u = (1 + r) f(R - 1,B)

where f(R - 1,B) is given by the theorem, and the given strategy
achieves this result.  On the other hand, if the next card is black,
you get to play with R red cards, B - 1 black cards, and starting
capital of 1 - r, so the best you can do is

  v = (1 - r) f(R,B - 1).

So the guarantee starting with R red and B black cards is the *worst*
of u and v.  That is, you have strategy S for deck(R,B) that starts by
betting of r on red and proceeds with the best possible strategy for
deck(R - 1,B) or deck(R,B - 1), whichever applies; then guarantee(S) =
min(u,v).

So you want to find the bet r that maximizes min(u,v), and if you can
achieve this maximum you have a strategy that achieves the best
possible guarantee, f(R,B).  But u and v are just linear functions of
r and the desired r is simply where they cross; set u = v and solve
for r:

  r = (p - q)/(p + q)   where  p = f(R,B - 1), and q = f(R - 1,B).

At this value of r, we get

  u = v = 2pq/(p + q).

It will be a bit easier to work with reciprocals:

  1/u = 1/v = (1/p + 1/q)/2.

So

  1/f(R,B) [Editor: "1/f(R + B,R)" in the original]
      = 1/u
      = (1/f(R,B - 1) + 1/f(R - 1,B))/2
         / C(R + B - 1,R)   C(R + B - 1,R - 1) \
      = (  -------------- + ------------------  ) (1/2)
         \  2^(R + B - 1)      2^(R + B - 1)   /

      = C(R + B,R) / 2^(R + B)

(You can easily observe that C(m - 1,n) + C(m - 1,n - 1) = C(m,n) by
looking at the construction of Pascal's triangle.)

So not only is the value of f(R,B) given by the formula in the theorem,
but the strategy of "bet r on red and follow the maximal strategy for
the resulting deck of cards" achieves this maximum value.

So in all cases starting with R + B = n + 1 cards, there is a strategy
that achieves f(R,B) whose value is given by the formula.  This
completes the induction, and proves the theorem.

Lemma:  f(R,B - 1) = (R/B) f(R - 1,B).
~~~~~

Proof:
                       (m + n)!          m     (m + n)!
  C(m + n,n + 1) = ----------------- = ----- * --------
                   (m - 1)! (n + 1)!   n + 1    m! n!

                 = (m/(n + 1)) C(m + n,n)

Let m = B, n + 1 = R:

               2^(R + B - 1)         2^(R + B - 1)
  f(R,B - 1) = -------------- = ------------------------
               C(R + B - 1,R)   (B/R) C(R + B - 1,R - 1)

             = (R/B) f(R - 1,B)

Corollary of the Theorem:  When there are R red cards and B black cards,
~~~~~~~~~~~~~~~~~~~~~~~~
(a) if R > B you should bet (R - B)/(R + B) of your capital on red;
(b) if B > R you should bet (B - R)/(R + B) of your capital on black;
(c) if R = B you should bet nothing.

Proof: If R = 0 or B = 0 the corollary says to bet all your capital on
the only kind of card remaining, just as described in that case in the
theorem.

If R > 0 and B > 0, the amount to bet is simply r on red (or -r on
black), where r is the value computed during the inductive step in the
proof of the theorem.  Then

  r = (p - q)/(p + q)   where  p = f(R,B - 1), and q = f(R - 1,B).

But according to the Lemma, p = (R/B)q, so set p = Rx, q = Bx.  Then

  r = (Rx - Bx)/(Rx + Bx)
    = (R - B)/(R + B)

If R > B, you bet this amount on red; if B > R, r is negative, so you
bet -r = (B - R)/(R + B) on black; and if R = B, then r = 0, so you
bet nothing.

-- David A. Karr <karr@cs.cornell.edu>