Weighing, searching and strategy puzzles

GAME · Chapter 516 min readAsked at Jane Street, SIG, Optiver, Citadel

Assumes Measuring and timing puzzles.

After this lesson you should be able to

  • Bound a search with an information argument before designing the search.
  • Balance a worst case rather than an average when the question says "guarantee".
  • Recognise the puzzles whose answer is a structure — a cycle, a parity, a square.

The second family asks you to find something with as few attempts as possible. Counting the information available tells you the answer is at least some number; a construction tells you it is at most that number; and when the two meet you are finished. Interviewers score the bound more than the construction, because the bound is the part that generalises.

Proposition 5.16

Bound first, construct second

Each attempt has a fixed number of distinguishable outcomes. If there are NN possibilities and each attempt has kk outcomes, no strategy can do better than ⌈log⁡kN⌉\lceil \log_k N \rceil attempts. Write that down before you design anything: it tells you whether to look for a cleverer scheme or to stop.

Holds when

  • A balance has three outcomes, so nn weighings separate at most 3n3^n cases.
  • A yes/no question has two, so nn questions separate at most 2n2^n.
  • The bound is only achievable if every attempt can be made equally informative.
Two weighings9Cases to separate24Three weighings27
Figure 5.17 · Why twelve coins need three weighings and not two. Twelve coins, either of which could be heavy or light, is 2424 cases. Two weighings separate nine, so two is impossible before any scheme is considered; three separate twenty-seven, so three might work — and it does, with almost nothing to spare.

Example 5.18

Twelve coins, one counterfeit

Twelve coins look identical. One is counterfeit and is either heavier or lighter — you do not know which. With a balance and three weighings, find it and say which way it differs.

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    3n≥2Nfor N coins3^{n} \ge 2N \quad \text{for } N \text{ coins}
  2. Substitute
    33=27≥24=2×123^3 = 27 \ge 24 = 2 \times 12
  3. Solve
    4 v 44 \text{ v } 4
    Balanced: the fake is among the other four, and two weighings separate eight cases.
  4. Tips: relabel and re-weigh mixing sides\text{Tips: relabel and re-weigh mixing sides}
    Move three from the heavy pan, three from the light pan and bring in known-good coins.
  5. Third weighing isolates one coin\text{Third weighing isolates one coin}
  6. Answer
    3 weighings, and 13 coins would be impossible3 \text{ weighings, and } 13 \text{ coins would be impossible}

Sanity check. Thirteen coins is 2626 cases, still under 2727 — but the first weighing cannot be made informative enough, so the bound is necessary and not sufficient. Saying that is worth more than the scheme.

Example 5.19

Two eggs and a hundred floors

You have two identical eggs and a hundred-storey building. An egg breaks above some floor and survives at or below it. Find that floor with as few drops as possible in the worst case.

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    n+(n−1)+⋯+1=n(n+1)2≥100n + (n-1) + \dots + 1 = \tfrac{n(n+1)}{2} \ge 100
  2. Substitute
    14×152=105≥100>91=13×142\tfrac{14 \times 15}{2} = 105 \ge 100 > 91 = \tfrac{13 \times 14}{2}
  3. Solve
    First drop at floor 14\text{First drop at floor } 14
    If it breaks, the second egg walks floors 1 to 13: 14 drops total.
  4. Then 14+13=27, 27+12=39, …\text{Then } 14+13 = 27,\ 27+12 = 39,\ \dots
    Each gap shrinks by one, so the worst case stays at 14.
  5. Answer
    14 drops14 \text{ drops}

Sanity check. Every path costs the same 1414 by construction. A strategy whose worst case varies between branches has not been balanced yet.

Why the gaps shrink by exactly one. After the first drop you have used one attempt, so whatever happens you have one fewer left. The next interval must therefore be one smaller, or its branch would cost more than the first one did. Balancing the worst case across every branch is the whole method, and it is the same argument that makes a fair market maker indifferent between being lifted and being hit.

The rest of this lesson is in Premium

You have read the opening. 12 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.