In an exchange argument for a greedy algorithm, what do you swap and what must the swap show?

## What a greedy correctness proof actually has to do A greedy algorithm commits to one irrevocable choice at a time and never reconsiders. That is why it is fast and why it is suspicious: nothing in the algorithm looks ahead, so nothing in the algorithm rules out the possibility that an early choice quietly destroys the best final answer. A correctness proof must close exactly that gap. It must show that committing to greedy's choice never costs you the optimum. An exchange argument is the standard way to close it, and its shape is worth memorising because interviewers ask you to reproduce the shape, not to invent a new proof on the spot. ## The invariant you are maintaining Before the mechanics, fix the statement being proved by induction: > After iteration *i*, the choices greedy has made so far extend to **some** optimal solution. Every word earns its place. "Extend to" means: there exists a complete optimal solution whose first *i* choices are exactly greedy's. "Some" means: there may be many optimal solutions, and greedy only has to be consistent with one of them. Candidates who state this as *the* optimal solution have already made the classic error — when several distinct answers achieve the same optimal value, greedy cannot be expected to match a particular one. When the invariant survives to the last iteration, greedy's complete output *is* an optimal solution, and the algorithm is correct. ## The exchange step The induction's base case is trivial: before any choice is made, the empty prefix extends to every optimal solution, and at least one exists. The inductive step is the exchange. Assume greedy's first *i* choices extend to an optimal solution *S*. Greedy now makes choice number *i+1*. Either *S* already contains that choice — nothing to do, the invariant carries over unchanged — or it does not. In the second case, build a new solution *S'* from *S* by removing whatever *S* used at that position and putting greedy's choice in its place, adjusting the rest of *S* as little as necessary. Two obligations, and a proof that skips either one is not a proof: 1. **Feasibility.** *S'* must still satisfy every constraint of the problem. This is where most exchange proofs actually do their work: showing that greedy's choice cannot conflict with the parts of *S* you kept. 2. **No worse.** The objective value of *S'* must be at least as good as *S*'s. Since *S* was optimal, *S'* is then optimal too. Notice the direction of that second obligation. You are *not* trying to prove greedy's choice is strictly better — that would contradict *S*'s optimality and is unprovable. You are proving greedy's choice is *free*: taking it costs nothing. Requiring strict improvement is the most common way a candidate ties themselves in knots at the whiteboard. ## Why the *first* disagreement Swapping at an arbitrary disagreeing position is legal but useless, because it gives no progress measure. By swapping at the earliest disagreement you keep the agreement prefix intact and lengthen it by exactly one, so the induction has something that strictly decreases: the number of positions where the optimal solution still differs from greedy. Finitely many exchanges therefore transform an arbitrary optimum into greedy's output without ever losing value. ## What the conclusion does and does not say It says greedy's output achieves the optimal objective value. It does not say the optimum is unique, does not say greedy is the only correct algorithm, and does not say anything about greedy's running time. It also says nothing about problems where the exchange fails — and when the exchange *does* fail, that failure is informative: the position where you cannot swap without breaking feasibility or losing value is usually exactly where a counterexample lives. ## Failure modes to avoid out loud - Comparing final totals ("greedy picked the biggest items, so its sum is biggest") — that is an assertion, not an argument. - Assuming the optimal solution is unique, then claiming greedy must equal it. - Forgetting feasibility: an exchange that improves the objective while violating a constraint proves nothing. - Proving only that the *first* choice is safe and stopping. One safe move is a base case; the induction is what turns it into a theorem. - Offering test cases in place of the argument. Any finite set of passing inputs is compatible with an algorithm that is wrong on the input you did not try.