How Many Rabbits Can You Pull out of a Hat?

A hat holds six toy rabbits: two orange, two green, two purple. You draw them one at a time without replacement, and before each draw you name a colour, scoring a point for each correct call. Knowing the full history of what has been drawn, and playing optimally, what is your expected score?

The Fiddler, Zach Wissner-Gross, February 28, 2025(original post)

Solution

At every draw the best guess is a colour with the most rabbits left, so the chance of being right is (largest remaining count)$/$(total remaining). Writing $E(\mathbf c)$ for the expected future score from counts $\mathbf c$, the first draw contributes $\max_i c_i/\!\sum_i c_i$ and then we average over which colour actually appears. Starting from $(2,2,2)$ this recursion gives $$E(2,2,2)=\boxed{\dfrac{101}{30}}\approx3.37.$$ With three colours level you are right with probability $\tfrac13$ on the opening draw, and the edge grows as the hat empties and the counts become lopsided.

The computation

Encode optimal play directly: from any colour counts, guess a most-common colour, add its hit probability, and recurse on each colour that might actually be drawn, weighting by its chance. Exact fractions throughout, memoised on the counts.

from fractions import Fraction as F
from functools import lru_cache
@lru_cache(None)
def E(c):
    tot = sum(c)
    if tot == 0: return F(0)
    val = F(max(c), tot)                              # best guess: a most-common colour
    for i, ci in enumerate(c):
        if ci:
            nc = list(c); nc[i] -= 1
            val += F(ci, tot) * E(tuple(nc))
    return val
print(E((2, 2, 2)))                                  # 101/30 = 3.3667

Extra Credit

Now the hat holds $30$ rabbits, ten of each colour. With the same optimal play, what is the expected score?

Solution

The identical recursion, started from $(10,10,10)$, gives $$E(10,10,10)=\frac{29551687577}{2156564410}\approx\boxed{13.70}.$$ A blind guesser would average $30/3=10$; the history-aware strategy adds about $3.7$ points. (The official extra-credit value is paywalled; this is my own.)

The computation

The same $E$ from the main section, evaluated at $(10,10,10)$.

print(E((10, 10, 10)), float(E((10, 10, 10))))       # 13.7031