Twenty Questions and the Entropy Bound

In twenty questions, one player thinks of something and the other must identify it using only yes/no questions, answered truthfully. With a good strategy, twenty questions is enough to pin down roughly a million distinct things. That number isn't a coincidence or folk wisdom — it falls directly out of counting how much a single yes/no answer can possibly narrow things down, and it's the same bound that shows up in every "identify one thing out of many, using few discrete tests" interview puzzle.

The core idea: one bit halves the space, at best

A yes/no question has exactly two possible answers. If the answer perfectly splits the remaining candidates into two equal halves, you eliminate exactly half of them regardless of which way it goes — that's the best any single question can do, because if the split is uneven, the unlucky branch (the larger half) leaves you with more work than an even split would have. After $q$ perfectly-balanced questions, the number of surviving candidates has been halved $q$ times, so it started at no more than $2^q$. Turning this around: to guarantee identifying one item out of $N$ possibilities, you need at least $q$ questions where $2^q \ge N$, i.e. $q \ge \log_2 N$. This is the entropy bound: $\log_2 N$ bits (questions) are necessary, and — if you can always find a perfectly balanced question — sufficient.

Worked example: why twenty questions covers about a million things

$2^{20} = 1{,}048{,}576$. So twenty perfectly-chosen yes/no questions can in principle distinguish just over a million distinct possibilities — which is why the game plausibly covers "any person, place, or thing" a casual player might think of, without needing more questions than a party game allows. Concretely: question 1 ("is it a living thing?") ideally splits the roughly-a-million-candidate mental space into two halves of about half a million each. Question 2 splits whichever half survived into quarters of the original. By question 20, in the best case, exactly one candidate remains — but only if every question actually achieves close to a 50/50 split of whatever's currently left, which is why skilled players ask broad, discriminating questions early rather than narrow, guess-like ones ("is it a cat?") that mostly waste a question's worth of potential information on a near-certain "no."

Worked example 2: applying the bound to a familiar puzzle

The 12-coin balance-scale puzzle (find one odd coin among 12, unknown direction, in 3 weighings) has $12 \times 2 = 24$ possibilities to distinguish. A weighing has 3 outcomes rather than 2, so the analogous bound is $3^w \ge 24$, giving $w \ge \log_3 24 \approx 2.89$, so $w=3$ weighings is the minimum integer satisfying the bound — matching the puzzle's known answer exactly, and confirming that 3 weighings is not just achievable but provably necessary, since 2 weighings only offer $3^2 = 9 < 24$ distinguishable outcomes.

What this means in practice

The entropy bound is the go-to sanity check for "is this proposed test/question/weighing plan even theoretically sufficient" before working out the details of how — compute the possibility count $N$, compute $\log_2 N$ (or $\log_k N$ for a $k$-outcome test), and compare it to the number of tests allowed. This same reasoning underlies why binary search is optimal for sorted lookups, why balanced decision trees classify efficiently, and why a well-designed due-diligence checklist asks broad discriminating questions before narrow confirmatory ones.