Logic puzzles: information bounds and common knowledge

GAME · Chapter 413 min readAsked at Jane Street, SIG, Optiver, IMC

Assumes Pricing a game: EV, re-rolls and when to stop.

After this lesson you should be able to

  • Bound a puzzle’s answer by counting information before searching for a strategy.
  • Distinguish what everyone knows from what is common knowledge.
  • Apply backward induction to a multi-agent puzzle.

Brainteasers look like a grab-bag, but interviewers are testing three specific habits: count the information available before you design a strategy, reason about what others know rather than only what you know, and work backwards from the end state. Each has a recognisable cue.

Proposition 4.1

Count the information first

Before searching for a weighing scheme or a questioning strategy, ask how much information each step can yield. A three-way balance gives log⁡23\log_2 3 bits per weighing, so nn weighings distinguish at most 3n3^n outcomes. That bound tells you immediately whether a solution can exist, and it usually tells you what the solution has to look like.

Holds when

  • A yes/no question yields one bit; a three-outcome balance yields log⁡23≈1.585\log_2 3 \approx 1.585 bits.
  • If the bound is tight, every step must be maximally informative — which forces the design.
  • A bound proves impossibility. It does not by itself produce a strategy.

Example 4.2

Counterfeit coins

Twelve coins, one counterfeit and either heavier or lighter. How many balance weighings are needed to find it and say which?

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    outcomes distinguishable in n weighings=3n\text{outcomes distinguishable in } n \text{ weighings} = 3^n
  2. Substitute
    outcomes to distinguish=12×2=24\text{outcomes to distinguish} = 12 \times 2 = 24
  3. Solve
    32=9<24≤27=333^2 = 9 < 24 \le 27 = 3^3
  4. n≥3n \ge 3
  5. Answer
    3 weighings, and 3 suffice3 \text{ weighings, and } 3 \text{ suffice}

Sanity check. The bound also rules out 14 coins (2828 outcomes) in three weighings. It does not promise 13 is achievable, and in fact 13 needs an extra known-good coin — a bound is necessary, not sufficient.

Definition 4.3

Common knowledge

Common knowledge — A fact is common knowledge when everyone knows it, everyone knows that everyone knows it, and so on without limit. That infinite tower is not pedantry: it is what makes the blue-eyed islanders puzzle work. Every islander already sees the blue eyes, so the visitor’s announcement tells nobody anything new — but it makes the fact common knowledge, and that is what starts the induction.

Derivation 4.4

The blue-eyed islanders

Islanders who deduce their own eye colour must leave that night. A visitor says aloud: "at least one of you has blue eyes."

  1. n=1: the single blue-eyed islander sees no others and leaves on night 1n = 1:\ \text{the single blue-eyed islander sees no others and leaves on night } 1

    The base case is where the announcement genuinely adds information.

  2. n=2: each sees one other; when that one stays, each deduces their own and both leave on night 2n = 2:\ \text{each sees one other; when that one stays, each deduces their own and both leave on night } 2
  3. n=k: nobody leaves for k−1 nights, then all k leave on night kn = k:\ \text{nobody leaves for } k-1 \text{ nights, then all } k \text{ leave on night } k
all n blue-eyed islanders leave on night n\text{all } n \text{ blue-eyed islanders leave on night } n

What the announcement actually changed. With n≥3n \ge 3 everyone already knows there is a blue-eyed islander, and everyone knows that everyone knows. What was missing was the top of the tower. Before the announcement the chain of "A knows that B knows that C knows..." terminated; afterwards it does not, and that is exactly what lets the induction run. The puzzle is a precise demonstration that shared information and common knowledge are different things — which matters on a trading floor, where a price everyone has seen behaves differently from one everyone knows that everyone has seen.

The rest of this lesson is in Premium

You have read the opening. 11 more sections follow, including 5 worked examples and 3 quick checks.

Start the free 7-day trialSign in

Nothing is charged for 7 days, and you can cancel before then. Or read Arithmetic that survives a clock in full, free.