Problem:
Alice knows that red cards and black cards will be revealed to her one at a time in random order. Before each card is revealed, Alice must guess its color. If Alice plays optimally, the expected number of cards she will guess correctly is , where and are relatively prime positive integers. Find .
Solution:
Answer (051):
An optimal strategy is for Alice to guess that the next card will be red unless there have been more red cards than black cards among previously seen cards, in which case she guesses black. Let be the probability that Alice guesses the th card correctly while using this strategy. With any strategy . For the second card, she will guess whichever color did not come first, so . The first two cards are the same color with probability , so
The first three cards are the same color with probability , so
The last two cards are the same color with probability , so
Finally, because Alice always knows the color of the last card. The expected number of cards Alice will guess correctly is the sum of the probabilities
The requested sum is .
Note: It is not coincidental that and . Notice that one of Alice's optimal strategies for the third card is to ignore the second card and simply guess the opposite of the first card because the color in the majority of the remaining cards after the first card is revealed cannot be in the minority after the second card is revealed. If she follows this strategy, her second and third guesses will be identical and determined by the first card, so . Similar comments apply to .
OR
Assume that the first card Alice sees has color X and the other color is Y . An optimal strategy for Alice is to guess red for the first card and to guess if the number of cards she has seen does not exceed the number of Y cards that she has seen. Alice guesses the first card correctly with probability . There are ways to arrange the remaining 2 X and 3 Y cards. In each of these 10 cases, one can calculate the number of the last five colors Alice guesses correctly using the stated optimal strategy, as shown in the table below.
| XXYYY | 3 | YXYXY | 5 |
|---|---|---|---|
| XYXYY | 3 | YXYYX | 4 |
| XYYXY | 4 | YYXXY | 4 |
| XYYYX | 3 | YYXYX | 3 |
| YXXYY | 4 | YYYXX | 3 |
Thus the expected number of cards that Alice will guess correctly is
as above.
OR
More generally, let be the expected number of cards guessed using an optimal strategy if there are red cards and black cards. If either or is 0 , then . Otherwise,
This recurrence relation can be iterated to complete the following table of values.
| r\b | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 3/2 | 7/3 | 13/4 |
| 2 | 2 | 7/3 | 17/6 | 18/5 |
| 3 | 3 | 13/4 | 18/5 | 41/10 |
The required value is , as above.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions