2023 AIME I Problem 6

Question

Alice knows that

3

red cards and

3

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

\frac{m}{n},

where

m

and

n

are relatively prime positive integers. Find

m + n.

Answer

Answer: 51

Concepts:expected value recursive probability optimization

Difficulty rating: 2600

Small hint:

Guessing the color with more cards remaining is optimal; let

E(r, b)

be the expected number correct with

r

red and

b

black left.

Big hint:

E(r,b) = \frac{\max(r,b)}{r+b}

+ \frac{r\,E(r-1,b) + b\,E(r,b-1)}{r+b};

build up from

E(1,1).

Solution:

Whatever Alice guesses, the deck evolves the same way; only the immediate success probability depends on her guess, so it is optimal to guess a color with the most cards remaining. Let

E(r, b)

be the expected number of correct guesses from a state with

r

red and

b

black cards left. Then

E(r, 0) = r,

E(0, b) = b,

and

\begin{aligned} E(r, b) &= \frac{\max(r, b)}{r + b} \\ &\quad {}+ \frac{r\,E(r-1,b)}{r+b} \\ &\quad {}+ \frac{b\,E(r,b-1)}{r+b}. \end{aligned}

By symmetry

E(r, b) = E(b, r).

Computing upward:

E(1,1) = \frac{3}{2},

E(2,1) = \frac{2}{3} + \frac{2 \cdot \frac{3}{2} + 2}{3} = \frac{7}{3},

E(2,2) = \frac{1}{2} + \frac{7}{3} = \frac{17}{6},

E(3,1) = \frac{3}{4} + \frac{3 \cdot \frac{7}{3} + 3}{4} = \frac{13}{4},

E(3,2) = \frac{3}{5} + \frac{3 \cdot \frac{17}{6} + 2 \cdot \frac{13}{4}}{5} = \frac{18}{5},

and finally

E(3,3) = \frac{1}{2} + \frac{18}{5} = \frac{41}{10}.

So the expected number of correct guesses is

\frac{41}{10},

and

m + n = 41 + 10 = 51.