I show you a shuffled deck of standard playing cards, one card at a time.

decision/red Added material

Problem

I show you a shuffled deck of standard playing cards, one card at a
time.  At any point before I run out of cards, you must say "RED!".
If the next card I show is red (i.e. diamonds or hearts), you win.  We
assume I the "dealer" don't have any control over what the order of
cards is.

The question is, what's the best strategy, and what is your
probability of winning ?

Show solution

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.

Additional material

[ Editor: a different proof, for the version in which you must take the
last card if you have not called before the end of the deck. ]

In article <729h7h$du1$1@nnrp1.dejanews.com>, <hochster@rocketmail.com> wrote:
> You and I play the following game. I turn over cards from a normal deck, one
> at a time, face up. At any time (including before I turn over the first card)
> you can declare that you want the next (face down) card. If this card is red,
> you win. Otherwise, you lose. If I get to the end of the deck, you must take
> the last card. Is there a strategy which wins this game with better than 50%
> probability? If not, why not?

All strategies win this game with 50% probability, so there is not.
To simplify things, reduce the deck to 2n cards, n marked `R' and n marked
`B'.  Suppose that, after we have seen a sequence (a,...,z) of cards drawn, our
strategy calls for us to look at the next card.  Then we will win when
the next card is R, i.e., when the overall sequence of draws starts with
S=(a,...,z,R); to get the probability of winning, we must sum the probabilities
of such Ss.  However, the probability of drawing some initial sequence of Rs
and Bs from the deck depends only on the number of Rs and Bs in the sequence.
Therefore, the probability of drawing S=(a,...,z,R) to start with
is the same as that of drawing T=(R,a,...,z) to start with.  If we sum the
probabilities of the Ts, we will find the win probability for the following
game: Draw the first card; if it is red, draw some more cards according to
our strategy and then win; otherwise, lose.  Since our original strategy
never directed us to skip more than 2n-1 cards before picking one, its
application in this new game always lets us win by the time we reach the
end of the deck, assuming the first card was red; so, this new game
is won just when the first card is red, and this happens with probability
50%.  The original game then also has win probability 50%.

I wanted to point out that there is a general sort of exchange principle
here.  For example, suppose that blackjack is played with two players,
the dealer and you.  The dealer draws two cards, one face-up and one
face-down; then you are dealt your hand and play, using some strategy;
then the dealer deals himself some extra cards, using a fixed algorithm
that only looks at his own hand, and your hands are compared to see who
wins.  Suppose that the dealer instead dealt himself his extra cards
before you played your hand.  How would it affect the probability of
your winning the hand?  The answer is that, if you used the same
strategy as before, the probability would be unaffected, provided only
that the deck cannot be exhausted during the play of the hand.  In fact:

  Suppose that A and B are playing a game, where each one has one turn at
  drawing cards from a deck, using some algorithm that looks only at his own
  cards to determine when he stops drawing, and where A's and B's hands are
  compared at the end to determine who wins.  Then the probability of A
  winning if he goes first is the same as the probability of A winning if B
  goes first. (We assume that the deck is never exhausted by any possible
  play.)

To apply this to the puzzle in this thread, let A draw until just before the
card whose color is crucial, let B draw the crucial card, and let the
comparison consist of checking B's card to see if it is red or not.

-- David Moews <dmoews@xraysgi.ims.uconn.edu>