Algorithms / Greedy Counterexamples
Least You Need to Know: Counterexamples to Tempting Greedy Rules
Many plausible greedy rules fail. The fastest way to disprove one is to build a small instance where the local rule makes an attractive first move but the final answer is worse than another feasible solution. Counterexamples are part of greedy mastery because they separate real proof from plausible storytelling.
The least you need to know
- A greedy rule is disproved by one concrete instance where it returns a suboptimal feasible answer.
- A useful counterexample should be as small and transparent as possible.
- The counterexample must compare the greedy output with a better feasible solution.
- A locally appealing rule can still be globally wrong.
- Failing to prove a greedy rule is not the same as disproving it; a counterexample is decisive.
Key notation
counterexample
one specific input where the claimed rule fails
feasible
satisfies the constraints even if not optimal
tempting greedy rule
a locally sensible but unproved choice rule
Tiny worked example
- Consider coin systems where 'take the largest coin first' seems natural.
- In a noncanonical system, that greedy rule may use more coins than another combination.
- Listing both outcomes on one tiny amount is enough to disprove the rule.
- No theorem can survive a single valid counterexample.
Common mistakes
- Students sometimes give an input where greedy fails to finish at all, but forget to show a better feasible solution exists.
- A huge messy instance is less convincing than a small clean one.
- A counterexample disproves the rule, not necessarily the entire problem family or all greedy ideas.
How to recognize this kind of problem
- The rule sounds locally sensible but lacks a proof.
- You can imagine a tiny instance where the first greedy step blocks a better later combination.
- The best response is to construct and compare explicit outputs.