Counting Information to Bound the Answer

Puzzles about weighings, yes/no questions, or guesses often ask for the minimum number needed in the worst case. Rather than trying strategies until you can't find a better one, you can often prove a floor directly: count how many distinct final outcomes the puzzle needs to tell apart, and note that each question can only cut that count down by a bounded factor. If the count doesn't fit, no strategy — however clever — can do it in fewer questions.

Worked example: the counterfeit coin, lower bound only

You have 12 coins, identical in appearance. Exactly one is counterfeit and weighs differently from the rest (you don't know if it's heavier or lighter). You have a balance scale. What is the minimum number of weighings needed, in the worst case, to find the counterfeit and say whether it's heavy or light — and why can't fewer weighings possibly work?

Count the outcomes you must distinguish. The counterfeit could be any of the 12 coins, and it could be either heavy or light — that's $12 \times 2 = 24$ possible final answers, and your strategy has to correctly announce which of the 24 it is.

Count what one weighing can tell you. A balance scale has exactly three possible readings each time you use it: left side heavier, right side heavier, or balanced. So $k$ weighings, in sequence, can produce at most $3^k$ distinct sequences of readings.

Set up the inequality. To have any hope of always identifying the right one of 24 outcomes, the number of distinguishable reading-sequences must be at least the number of outcomes: $3^k \geq 24$.

Solve it. $3^2 = 9$, too small. $3^3 = 27 \geq 24$. So $k \geq 3$: at least 3 weighings are required, and this bound alone rules out any 2-weighing strategy before you've tried to design one. (A matching 3-weighing strategy exists, which shows the bound is tight — but that construction is a separate puzzle.)

The same counting proves that guessing a number between 1 and $N$ with yes/no questions needs at least $\lceil \log_2 N \rceil$ questions (each question halves the outcomes at best), and that identifying one fake coin among $n$ using a balance needs at least $\lceil \log_3 n \rceil$ weighings when you already know the direction of the fake.

This is the same reasoning behind coding-theory bounds on compression and hashing: you cannot losslessly compress every one of $N$ distinct messages into fewer than $\log_2 N$ bits, because a shorter code simply doesn't have enough distinct patterns to go around.