<pre>
If a deck has n cards, r red and b black, the best strategy wins
with a probability of r/n.  Thus, you can say "red" on the first card,
the last card, or any other card you wish.
Proof by induction on n.  The statement is clearly true for one-card decks.
Suppose it is true for n-card decks, and add a red card.
I will even allow a nondeterministic strategy, meaning you say "red"
on the first card with probability p.  With probability 1-p,
you watch the first card go by, and then apply the "optimal" strategy
to the remaining n-card deck, since you now know its composition.
The odds of winning are therefore: p * (r+1)/(n+1)  +
        (1-p) ''' ((r+1)/(n+1) ''' r/n  +  b/(n+1) * (r+1)/n).
After some algebra, this becomes (r+1)/(n+1) as expected.
Adding a black card yields: p * r/(n+1)  +
        (1-p) ''' (r/(n+1) ''' (r-1)/n  +  (b+1)/(n+1) * r/n).
This becomes r/(n+1) as expected.
</pre>
