Contradiction and counter­examples

Two more tools. Proof by contradiction shows a claim is true by showing that its opposite is impossible. A counterexample shows a claim is false with a single input.

Proof by contradiction

To prove a claim by contradiction:

1. Assume the claim is false.
2. Reason from that assumption, one correct step at a time.
3. Reach something impossible, such as a number that is both even and odd.

Every step was correct, so the only thing that can be wrong is the assumption. So the claim is true. This method suits claims of the form “there is no …” or “it is impossible to …”, which are hard to prove directly. The proof that sorting needs about n log n comparisons, n times the number of times n can be halved (SORT-5), has this shape.

Example: a repeat must exist

Claim: if a list holds 11 whole numbers, each from 1 to 10, then some number appears at least twice.

Assume the opposite: all 11 numbers are different. There are only 10 possible values, from 1 to 10. Eleven different numbers would need 11 different values. That is impossible. So the assumption was false, and some number must repeat.

This is called the pigeonhole principle: if you put more items than boxes, some box gets two items. It proves that a repeat exists, without saying which number repeats. It shows up in hashing (HASH), in cycle detection, and in many proofs that a task needs at least a certain number of steps.

One counterexample is enough

A claim like “this function is correct” is about every valid input. To prove it false, you need only one valid input where it fails. That input is called a counterexample.

The two directions are not equal. A thousand passing inputs do not prove a function correct. One failing input proves it wrong. So when you suspect a claim, the fastest way to decide is often to look for a counterexample first. If you cannot find one, the search usually shows you why the claim is true, and that becomes the proof.

Example: making change with coins

Claim: to make an amount with the fewest coins, always take the biggest coin that fits, and repeat. This is called a greedy method: it makes the choice that looks best right now, and never goes back. With Indian coins of 1, 2, 5 and 10 rupees, it works. But is it true for every set of coins? Step through the figure, which uses coins of 1, 3 and 4.

For 7, greedy takes 4 and then 3, which is best. For 6, greedy takes 4, 1 and 1: three coins. But 3 + 3 makes 6 with two. So the claim is false, and the amount 6 with coins 1, 3, 4 is a counterexample. The GRDY station shows how to prove when greedy methods do work, and DYNP shows how to solve this coin problem correctly.

How to find a counterexample

• Try the edges first. Empty input, one value, all values equal, negative numbers, the answer at the very start or end.
• Try all small inputs. Many bugs show up on inputs of size 3 or 4. A loop can try every small input in a fraction of a second, as the next lesson shows.
• Test the reasoning. Find the step in the argument you are least sure of, and build an input that breaks exactly that step.

from itertools import product

# Try every list of length 0 to 4 with values 0 to 3.
for n in range(5):
    for a in product(range(4), repeat=n):
        a = list(a)
        if fast(a) != slow(a):
            print("counterexample:", a)