14.19 Counterexamples
A counterexample is a small input that disproves a proposed algorithm, lemma, or proof idea.
14.19 Counterexamples
A counterexample is a small input that disproves a proposed algorithm, lemma, or proof idea. In greedy algorithm design, counterexamples are especially valuable because many greedy rules look plausible before they are tested.
A good counterexample does more than show that an algorithm is wrong. It explains why the greedy choice is wrong. It reveals which local score is misleading, which constraint was ignored, or which exchange argument cannot be completed.
This recipe shows how to construct counterexamples for greedy algorithms systematically.
Problem
You have a proposed greedy rule.
Examples:
Choose the earliest starting interval.
Choose the shortest interval.
Choose the highest-value item.
Choose the largest coin.
Choose the nearest station.
You need to determine whether the rule is correct.
If it is wrong, find a small input where it fails.
Why Counterexamples Matter
Greedy algorithms often fail for structural reasons.
A counterexample exposes those reasons quickly.
Consider the rule:
For interval scheduling, choose the earliest starting interval.
This sounds reasonable. Starting early seems productive.
But the rule fails:
| Interval | Start | End |
|---|---|---|
| A | 1 | 10 |
| B | 2 | 3 |
| C | 3 | 4 |
| D | 4 | 5 |
The greedy rule chooses:
A
Optimal solution:
B C D
The counterexample shows the flaw: early start time does not preserve future capacity.
Recipe: Build a Counterexample
Use this process when testing a greedy rule.
Step 1: Identify the Greedy Score
Ask what the algorithm optimizes locally.
Examples:
| Greedy Rule | Local Score |
|---|---|
| Earliest start | Smallest start time |
| Shortest interval | Smallest duration |
| Highest value | Largest value |
| Largest coin | Largest denomination |
| Nearest station | Smallest distance |
The counterexample should make that local score attractive but globally harmful.
Step 2: Create a Trap Item
Construct one candidate that looks best locally.
For interval scheduling:
A = [1, 10]
It starts earliest.
For knapsack:
A = weight 10, value 60
It has the highest density.
For coin change:
coin 4
It is the largest coin less than the target.
Step 3: Create a Better Combination
Add several candidates that the trap blocks.
For interval scheduling:
B = [2, 3]
C = [3, 4]
D = [4, 5]
For knapsack:
B + C
may beat:
A + B
For coin change:
3 + 3
beats:
4 + 1 + 1
The pattern is:
One locally attractive choice
versus
several globally better choices
Step 4: Keep It Small
A counterexample should be as small as possible.
Small examples are easier to understand, easier to test, and harder to dismiss.
For many greedy failures, three or four items are enough.
Counterexample: Shortest Interval
Proposed rule:
Choose the shortest interval first.
Input:
| Interval | Start | End | Length |
|---|---|---|---|
| A | 1 | 4 | 3 |
| B | 4 | 7 | 3 |
| C | 3 | 5 | 2 |
Greedy chooses:
C
No other interval is compatible with C.
Greedy result:
1 interval
Optimal result:
A B
which has:
2 intervals
The shortest interval sits across the boundary between two compatible intervals. It is locally compact but globally destructive.
Counterexample: Highest Value in Knapsack
Proposed rule:
Choose highest-value item first.
Capacity:
10
Items:
| Item | Weight | Value |
|---|---|---|
| A | 10 | 100 |
| B | 6 | 70 |
| C | 4 | 50 |
Greedy chooses:
A
Total value:
100
Optimal:
B + C
Total value:
120
The single highest-value item blocks a better combination.
Counterexample: Highest Density in 0/1 Knapsack
Proposed rule:
Choose highest value density first.
Capacity:
50
Items:
| Item | Weight | Value | Density |
|---|---|---|---|
| A | 10 | 60 | 6 |
| B | 20 | 100 | 5 |
| C | 30 | 120 | 4 |
Greedy chooses:
A + B
Value:
160
Optimal:
B + C
Value:
220
Density works for fractional knapsack because capacity can be exchanged continuously. It fails here because items are indivisible.
Counterexample: Largest Coin
Proposed rule:
Use the largest coin not exceeding the remaining amount.
Coins:
4, 3, 1
Amount:
6
Greedy:
4 + 1 + 1
Uses:
3 coins
Optimal:
3 + 3
Uses:
2 coins
The largest coin creates a poor remainder.
Counterexample: Nearest Refueling Station
Proposed rule:
Always stop at the nearest reachable station.
Target:
100
Start fuel:
50
Stations:
| Position | Fuel |
|---|---|
| 25 | 25 |
| 50 | 50 |
Nearest-stop greedy chooses station 25 first.
Then it may still need station 50.
A better strategy delays the stop and uses the larger station at 50.
The flaw is that distance alone does not measure future reach.
Counterexample: Sorting by Start Time for Meeting Rooms
Some interval problems require sorting by start time. Others require sorting by end time. Mixing them up leads to wrong algorithms.
For selecting maximum non-overlapping intervals, start-time sorting fails.
Input:
| Interval | Start | End |
|---|---|---|
| A | 1 | 100 |
| B | 2 | 3 |
| C | 3 | 4 |
| D | 4 | 5 |
Start-time greedy chooses:
A
Optimal chooses:
B C D
The correct ordering is by finish time.
Minimality
After finding a counterexample, try to shrink it.
Ask:
- Can one item be removed?
- Can values be smaller?
- Can times be shorter?
- Can two cases be merged?
- Can the same failure happen with three objects instead of four?
A minimal counterexample is more persuasive and easier to remember.
For example, the shortest-interval counterexample uses only three intervals:
| Interval | Start | End |
|---|---|---|
| A | 1 | 4 |
| B | 4 | 7 |
| C | 3 | 5 |
That is better than a larger schedule with the same failure.
Counterexamples and Proof Attempts
Failed proof attempts often point directly to counterexamples.
Suppose you try to prove:
The shortest interval can appear first in some optimal schedule.
The proof fails when the shortest interval overlaps two compatible intervals.
Turn that failure into data:
Left compatible interval
Short middle interval
Right compatible interval
That structure becomes the counterexample.
This is a practical technique: when an exchange argument fails, instantiate the failure.
Testing Greedy Implementations
Counterexamples should become test cases.
Example in Go:
func TestGreedyKnapsackDensityFails(t *testing.T) {
items := []Item{
{Weight: 10, Value: 60},
{Weight: 20, Value: 100},
{Weight: 30, Value: 120},
}
got := GreedyKnapsackByDensity(items, 50)
if got == 220 {
t.Fatalf("unexpectedly got optimal result")
}
}
For a production-quality test, you would compare a candidate greedy implementation against a brute-force solver on small inputs.
Brute Force as a Counterexample Generator
For small input sizes, brute force can automatically find counterexamples.
The workflow is:
Generate small random inputs.
Run greedy algorithm.
Run exact algorithm.
Compare results.
Stop on mismatch.
This is one of the most effective ways to test greedy ideas.
For interval scheduling, exact search can enumerate all subsets.
For knapsack, exact search can enumerate all item combinations.
For coin change, dynamic programming can provide the exact answer.
Go Sketch
func FindCounterexample() {
for trial := 0; trial < 10000; trial++ {
input := RandomSmallInput()
greedy := Greedy(input)
exact := Exact(input)
if greedy != exact {
fmt.Println("counterexample:", input)
return
}
}
}
This approach does not prove correctness, but it is very good at detecting incorrect greedy rules.
Common Counterexample Shapes
Many greedy failures fit one of these templates.
| Shape | Description |
|---|---|
| Trap item | One attractive item blocks many smaller better ones |
| Bad remainder | Local choice leaves an inefficient leftover |
| Boundary blocker | Short interval overlaps two compatible intervals |
| Delayed value | Best choice appears worse until later |
| Tight deadline | Wrong early choice blocks urgent later work |
| Indivisibility | Fractional exchange is impossible |
| Tie failure | Equal scores need careful tie-breaking |
Learning these shapes makes counterexample construction faster.
When No Counterexample Appears
Failing to find a counterexample does not prove correctness.
It only means the tested cases did not break the rule.
To establish correctness, you still need one of the proof tools from earlier sections:
- Greedy-choice property
- Exchange argument
- Cut property
- Monotonicity
- Matroid structure
Counterexamples disprove algorithms. Proofs validate them.
Both are necessary.
Takeaway
Counterexamples are essential tools for greedy algorithm design. A good counterexample isolates the flaw in a local decision rule by making the greedy choice attractive but globally harmful. Most counterexamples are small and follow recurring shapes: trap items, bad remainders, boundary blockers, delayed value, and indivisibility. Before attempting a full correctness proof, try hard to break the greedy rule. If it fails, the counterexample teaches you why. If it survives, you still need a proof, but you have a stronger candidate algorithm.