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:
We break the problem into stages, one for each card revealed, then further into cases based on the number of remaining unrevealed cards of each color. Since expected value is linear, the expected value of the total number of correct card color guesses across all stages is the sum of the expected values of the number of correct card color guesses at each stage; that is, we add the probabilities of correctly guessing the color at each stage to get the final answer (See https://brilliant.org/wiki/linearity-of-expectation/)
At any stage, if there are unrevealed cards of one color and of the other color, and , then the optimal strategy is to guess the color with unrevealed cards, which succeeds with probability .
Stage 1
There are always unrevealed cards of each color, so the probability of guessing correctly is .
Stage 2
There is always a split ( unrevealed cards of one color and of the other color), so the probability of guessing correctly is .
Stage 3
There are now cases:
Thus, the overall probability of guessing correctly is .
Stage 4
This stage has cases as well:
The probability of guessing the fourth card correctly is therefore .
Stage 5:
Yet again, there are cases:
In total, the fifth card can be guessed correctly with probability .
Stage 6:
At this point, only card remains, so the probability of guessing its color correctly is .
In conclusion, the expected value of the number of cards guessed correctly is
so the answer is .
The problems on this page are the property of the MAA's American Mathematics Competitions