Section 29.3

Scheduling and Clever Constructions

Grill and toast scheduling, minimal sets of bills, the double-padlock exchange, blind coin splits, spreading infection in pairs.

Toolkit

These problems hinge on turning a physical process into a counting or invariant argument: find a quantity that bounds the schedule’s length, then exhibit a construction matching that bound.

Key techniques:

Counting lower bounds: tally the total “slots” needed (e.g. side-cookings, bills of each denomination) and divide by the capacity per step to force a minimum number of rounds or items; then construct a rotation/assignment achieving it exactly.
Worst-case forcing: if a single amount or configuration requires $k$ copies of some unit, that same stock must suffice for all smaller or related cases—check it does.
Sequential commuting operations: when two parties each hold a key/lock and operations must commute (lock/unlock), order the steps so each party’s own action is always invertible by themselves alone.
Parity/counting tricks for blind protocols: splitting a set with $m$ heads among $n$ total by isolating $m$ items and flipping them exploits $m - (\text{heads in subset}) = \text{heads outside}$ .
Doubling/branching invariants: if each infected agent infects at most one other per round, $|I_{t+1}| \le 2|I_t|$ , giving minimal time $n = \lceil \log_2 N \rceil$ ; to slow spread, keep contact graphs partitioned into closed clusters admitting at most one new entrant per round.

Problems