Info-theoretic lower bounds: counting hypotheses vs. outcomes
If you must distinguish $2^n$ hypotheses but each query has fewer than $n$ bits of resolution, you can't possibly succeed. Pure counting; no algorithm matters.
Some puzzles ask: what’s the minimum number of weighings to find the odd ball? Pure counting tells you the floor. With 12 balls and one possibly heavier or lighter, you have 24 “truths” to distinguish. A balance scale answers tilt-left, tilt-right, or balance — 3 outcomes. With $k$ weighings you can encode at most $3^k$ results, so you need $3^k \geq 24$, i.e. $k \geq 3$. We’ll see exactly this bound.
✓ Intro · expand
Try first (productive failure)
Before the worked example: spend 60 seconds taking your best shot at this.
A guess is fine — being briefly wrong about a problem makes the explanation
land harder when you read it. This appears once per tutorial; skip
if you already know the trick.
60s
✓ Try first · expand
Worked example
You have 12 identical-looking balls. Exactly one is the odd ball — it is either heavier or lighter than the others, but you don’t know which. Using a balance scale (each weighing outputs left heavier, right heavier, or balanced), what is the minimum number of weighings needed to identify the odd ball and say whether it is heavy or light?
✓ Worked example · expand
Practice 1 of 3Type a fraction, decimal, or expression — mathjs parses it.
✓ Practice · expand
Reflection
Why does the lower bound only depend on counts $H$ and $b$ — not on the structure of the problem? When the bound is $k$ but a clever strategy can’t reach $k$, what does that asymmetry tell you about the problem? (Hint: think about what guarantees the bound makes — and doesn’t make.)