### Usenet Newsgroups

# Rec.Puzzles Hall of Fame

The rec.puzzles Hall of Fame is a compilation of over 500 of the most popular puzzles that have been posted and discussed in the rec.puzzles newsgroup. In most cases a detailed solution has been provided. Many of these puzzles also appear in Braingle's own collection.

Categories

## decision : red.p

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 ?

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

## Follow Braingle!