Constructing Minimal Counterexamples to Disprove Algorithmic Ideas

Welcome back. In the previous lesson, you separated necessary from sufficient conditions: an observation may rule instances out without guaranteeing a construction, or it may guarantee a construction without covering every valid case.

A counterexample is the fastest way to expose that missing direction. It is also a core contest skill: instead of spending 20 minutes polishing an attractive idea, you try to break it immediately with the smallest legal input that targets its weakness.

This lesson develops a deliberate method for constructing such inputs. The goal is not merely to notice that an algorithm is wrong, but to produce a compact, rigorous witness showing exactly why it is wrong.

---

A counterexample is a disproof with four parts

Suppose you propose an algorithm $A$ for a problem with valid-input set $\mathcal{V}$. A correctness claim says:

$$\forall I\in \mathcal{V},A(I)\text{ is correct}.$$

You disprove this universal claim by finding one valid instance $I$ on which the algorithm fails.

For an optimization problem, a complete counterexample must show:

1. The input is valid. It obeys every constraint and structural requirement.
2. The proposed rule makes a specific choice. Ideally, that choice is forced rather than dependent on a tie.
3. The rule’s final result. State the objective value or constructed object it returns.
4. A better valid result. Exhibit a witness, not just the assertion “the optimum is better.”

For a maximization problem, the essential inequality is:

$$\mathrm{value}(A(I))<\mathrm{OPT}(I).$$

For minimization, reverse the inequality. For decision and construction problems, failure may instead mean that the algorithm outputs YES for an impossible input, outputs NO for a feasible one, or constructs an invalid object.

A different answer is not automatically a failure. If two different schedules both contain the maximum possible number of meetings, both are correct. Compare against the specification: validity, feasibility, or objective value.

This directly continues the previous lesson’s logic:

• To refute “$C$ is necessary,” find a solvable instance where $C$ fails.
• To refute “$C$ is sufficient,” find an impossible instance where $C$ holds.
• To refute “this greedy rule is always optimal,” find one input where its locally preferred choice destroys the global optimum.

---

Start from the vulnerable commitment

Most incorrect greedy ideas have the same underlying flaw: they commit to a feature that looks good now but consume a resource needed later.

Common resources include:

• remaining time in scheduling;
• capacity in a construction;
• unused vertices or edges in a graph;
• available sum in coin change;
• a small number of allowed operations;
• a prefix or suffix that future choices must remain compatible with.

When testing a proposed rule, do not generate random large cases first. Instead, ask:

What must be true for this local choice to become regrettable?

Usually you need only two competing futures:

• the greedy choice, which blocks many good options; and
• a slightly less attractive first choice, which permits a better continuation.

Consider the tempting shortest-path idea:

“From the current vertex, always take the outgoing edge of smallest weight.”

The first edge on the upper route has cost $1$, smaller than $20$ and $30$, so the bad rule is forced to select it. But its total route cost is

$$1+100+200=301.$$

The middle route has total cost

$$20+3+2=25.$$

This is a valid counterexample because it gives both sides: the algorithm’s route and a strictly better route.

Notice the precision here. This does not disprove Dijkstra’s algorithm. Dijkstra does not permanently commit to “the smallest edge leaving the current vertex”; it maintains and compares tentative total distances. A counterexample only disproves the exact algorithmic claim you stated.

---

A compact counterexample pattern: interval scheduling

Take the classic problem:

Select the maximum number of pairwise non-overlapping intervals.

Suppose someone suggests this rule:

Repeatedly choose the interval with the earliest start time.

The likely weakness is clear: an interval can start early yet occupy almost the entire timeline. To exploit that weakness, make the earliest-starting interval long enough to block two compatible intervals.

Example 1: earliest start time fails

Use these three intervals:

$$(1,10),(2,4),(5,7).$$

Assume intervals that meet at an endpoint are compatible; that convention does not affect this example.

The earliest-start rule chooses $(1,10)$. It overlaps both remaining intervals, so the algorithm gets only one meeting.

But the pair

$$\{(2,4),(5,7)\}$$

is compatible and has size two. Therefore, earliest start time is not a correct greedy rule.

This example is not merely small; it is minimal by number of intervals for this type of failure. With only two intervals:

• if the two intervals overlap, no solution can schedule both;
• if they do not overlap, choosing either one still leaves the other available.

So a strict gap between a greedy answer of one and an optimal answer of two requires at least three intervals: one harmful choice and two mutually compatible alternatives.

That minimality argument matters. It explains the shape of the bug rather than just presenting a memorized test.

Example 2: shortest duration fails

Now try another appealing rule:

Repeatedly select the shortest available interval.

Use:

$$(5,7),(2,6),(6,10).$$

The interval $(5,7)$ has duration $2$, while the other two have duration $4$. Thus the greedy choice is forced: there is no tie to hide behind.

However, $(5,7)$ overlaps both other intervals, so the greedy result has size one. The intervals $(2,6)$ and $(6,10)$ are compatible and yield size two.

The design pattern is worth retaining:

Make the greedy object uniquely attractive according to its local score, but arrange it to overlap several objects that work together.

This is much more useful than trying to remember particular endpoints.

---

Make “minimal” a deliberate objective

In contest discussion, “minimal counterexample” often means “small enough to inspect immediately,” not necessarily mathematically smallest under every possible measure. Be explicit about the measure you are minimizing.

A practical reduction order is:

1. Number of objects: array length, vertices, intervals, operations, or items.
2. Structural complexity: number of edges, branches, distinct values, or special cases.
3. Magnitude: small coordinates, small weights, small values.
4. Ambiguity: remove ties unless ties are the subject of the bug.

Small examples are better because you can trace every decision manually. They also make flawed proof claims visible. If an explanation needs 50 elements before it breaks, it is often still hiding the actual reason it breaks.

A strong workflow is:

1. State the alleged greedy rule exactly.
2. Identify the irreversible or costly commitment.
3. Build the smallest skeleton where a bad first choice blocks a better future.
4. Make the bad choice uniquely preferred, if possible.
5. Write down both the greedy result and the better witness.
6. Delete or simplify anything that is not needed for the failure.

For example, consider the coin-change rule “take the largest coin not exceeding the remaining amount.” With denominations $1,3,4$ and target $6$, greedy selects:

$$4+1+1,$$

using three coins. But:

$$3+3$$

uses two coins. The target and denomination set are tiny because the construction needs only one locally larger coin that leaves an awkward remainder, plus two medium coins that fit together exactly.

---

Ties: does your example break the algorithm or only one implementation?

Tie handling is a frequent source of false confidence. Suppose an informal rule says:

“Pick a best-looking option.”

What happens when several options look equally good?

There are two useful categories:

Type	Meaning	What it establishes
Plausible counterexample	At least one legal tie resolution causes failure	The underspecified greedy idea is not guaranteed correct
Definitive counterexample	Every possible tie resolution causes failure	The rule fails regardless of implementation details

A definitive counterexample is stronger because it avoids arguments such as “my sort order happens to choose the other one.” The interval examples above are definitive: the harmful first interval is uniquely earliest or uniquely shortest.

For a deterministic program, tie-breaking is part of the algorithm. “Sort by weight” is incomplete if equal weights can occur. The actual program may sort by index, input order, another field, or an unstable implementation-dependent order.

So when debugging a submission, test the implemented rule:

• What order does the code actually use?
• Does it use strict or non-strict comparisons?
• Does it treat equal endpoints as overlapping?
• Does it accidentally rely on input order?

When disproving a high-level idea, force strict inequalities whenever you can. It makes the proof cleaner and eliminates irrelevant implementation debates.

---

From a wrong answer to a useful failing test

A counterexample is not only a proof tool. It is the most useful artifact after a Wrong Answer verdict. Once you have a failing input, shrink it while preserving the failure.

The key preservation test is:

The input remains valid, and the candidate solution still disagrees with the expected result.

Reduce in a disciplined order:

• Remove an array element, interval, edge, or operation.
• If it still fails, keep the deletion.
• Replace large values with smaller values.
• Collapse unnecessary distinct values.
• Remove a graph edge while keeping required connectivity or other input constraints.
• Eliminate ties if they are not central to the defect.

A smaller case can take a mysterious implementation failure and turn it into a one-sentence explanation: “I committed to the middle edge and therefore lost the two edges that form the optimum matching.”

Random testing can discover a failing case, but deliberate construction tells you where to look. For greedy logic, start with adversarial shapes rather than uniform randomness:

• a long interval plus two short compatible ones;
• a cheap first edge with expensive forced continuation;
• a locally cheap item that consumes a scarce resource;
• a central graph vertex whose selection blocks many mutually compatible vertices;
• equality boundaries, empty choices, and smallest legal sizes.

Later in the course, you will automate this with brute-force oracles and stress tests. For now, the important habit is conceptual: every attractive rule should face a targeted attack before you invest in proving or coding it.

---

A contest-ready counterexample note

When a candidate idea appears, write a short note like this before committing:

Claim being tested: choose the locally smallest next edge.
Vulnerability: a cheap edge can lead to an expensive forced suffix.
Smallest skeleton: source, destination, and two alternative routes.
Forced choice: first edge costs $1$, alternatives cost $20$ and $30$.
Failure: greedy total $301$; valid route of cost $25$.

This takes less than a minute. If you cannot construct a counterexample after serious targeted attempts, that does not prove the rule correct—but it tells you the next step should be a proof attempt, usually an exchange argument or an invariant.

---

Takeaways

A minimal counterexample is a small valid input that exposes a precise contradiction between an algorithm’s result and the problem’s requirement.

To construct one:

• state the algorithm and its tie behavior precisely;
• identify the local commitment that could damage future options;
• build the smallest structure with a better alternative future;
• force the bad choice when possible;
• show both the algorithm’s output and a better valid witness;
• shrink the input without losing validity or failure.

Counterexamples also enforce logical discipline. A solvable instance violating a claimed condition refutes necessity; an impossible instance satisfying it refutes sufficiency; a better witness refutes optimality.

Next, you will move from breaking incorrect processes to justifying correct ones: stating an invariant that explains why an iterative or constructive algorithm remains correct at every step.