Section 28.3

Adversarial Search

Egg drop, guessing a number by halving, 25 horses, worst-case key-lock matching.

Toolkit

These problems share an adversarial, worst-case framework: an adversary chooses outcomes (or the hidden value) to maximize your cost, and you must choose a strategy minimizing that worst case. The key tool is to bound, at each step, how much information a single query can extract, then balance the “shrinking budget” across steps so the worst case stays constant or decreases uniformly.

With $k$ binary (higher/lower) queries, at most $2^k-1$ candidates can be fully resolved.
Elimination principle: if all but one candidate have been tested, the last is known for free — worst case for full identification among $n$ items is $(n-1)+(n-2)+\cdots+1=\binom{n}{2}$ .
Egg-drop recursion: if $f(d,e)$ is the maximum floors distinguishable with $d$ drops and $e$ eggs, $f(d,e)=f(d-1,e-1)+f(d-1,e)+1$ ; for $e=2$ , $f(d,2)=d(d+1)/2$ .
Comparison-based tournaments: a round narrows candidates to those consistent with all observed orderings; count surviving possibilities before finalizing with extra comparisons.
General strategy: minimize worst-case queries by making each query’s two outcome branches as balanced as possible in remaining uncertainty.

Problems