Why doesn't a greedy rule passing every test case you tried prove it optimal?

## What a greedy algorithm is claiming A greedy algorithm makes one irrevocable choice at each step by a local rule and never reconsiders. That is an extraordinarily strong claim: that a decision made with no knowledge of the rest of the input is never regretted. Two properties have to hold for it. - **The greedy-choice property.** There exists an optimal solution that agrees with the choice the rule makes first. If that holds at every step, the rule can be followed all the way down without ever leaving optimality behind. - **Optimal substructure.** After the choice is fixed, what remains is a smaller instance of the same problem, and solving that optimally completes an optimal whole. The second is shared with dynamic programming and is not what usually breaks. The first is what greedy rules die on, and it is the one nobody proves. ## Why the test suite cannot supply the proof A correctness claim is universally quantified: *for every* input, the rule's output cost equals the optimum. A test run is an existential observation: *for these* twelve inputs, it did. No number of passing samples closes that gap, and the gap is not small, because the inputs that break greedy rules are not spread uniformly through the space. They are narrow and structured — the tie, the value just under a threshold, the cluster that sits one unit outside a window. Hand-written test cases and uniform random generators both under-sample exactly the region where greedy rules fail, because a human writes the case they were already thinking about and a uniform generator almost never lands on a boundary configuration. ## Reading the pass-buying rule The fragment walks the travel dates in order. At the first date not yet covered, it counts how many travel dates fall inside a season-length window; if that count reaches the season break-even, it buys the season pass and jumps past the window. Otherwise it tries the same test at week length, and failing both it buys a single fare and advances one date. Every clause is locally reasonable, and the rule is internally consistent — there is no off-by-one to find. The question is whether starting with the largest qualifying pass is ever wrong. Consider travel that is sparse for a stretch and then dense just after the window the rule would buy: opening with a *smaller* purchase can realign the later, larger pass so it swallows the dense stretch, and the total falls. The rule cannot see that, because it decides using only the dates inside the current window. The property it needs — that some optimal plan opens with this pass — is precisely the thing that fails. ## What actually settles the question - **To claim optimality:** a proof of the greedy-choice property at each step. Nothing weaker is a claim; it is a hope. - **To refute optimality:** one input on which the rule's cost exceeds the true optimum. That is why differential search — generate structured inputs, run the rule against an exhaustive or tabulated solver, compare costs — is such good value. It cannot prove the rule right, but it finds the counterexample far faster than intuition does, and finding one ends the argument. Note the asymmetry: evidence of a bug is cheap and conclusive; evidence of correctness is expensive and only ever a proof. ## The mirror mistake, which is just as common Having found a counterexample, the reflex is "so it is dynamic programming". That does not follow either. One counterexample establishes exactly one thing: *this rule* is not optimal. It leaves open that a different local rule is provably optimal (many problems have a non-obvious ordering that works), that the problem admits a clean recurrence with a small state space, or that neither applies and the practical answer is search with pruning. Two failed candidate rules do not add up to a theorem about the problem, in either direction. So the discipline is symmetrical. Do not promote a rule to "correct" on the strength of samples, and do not condemn a paradigm on the strength of one broken instance of it. Each direction has its own obligation: a proof going one way, a counterexample going the other. ## What good sounds like in the room When you propose a greedy solution, propose it with its proof obligation attached: "I'll take the largest qualifying pass first — that is optimal if I can show some optimal plan opens with it, and here is my argument." If the argument does not come, say so and start looking for the counterexample yourself. Interviewers are far more impressed by a candidate who says "I cannot justify this greedy choice, so let me look for a case where an earlier small purchase realigns a later big one" than by one who runs three examples and declares victory.