Competition mathematics and problem solving

Proof by contradiction

A proof technique that assumes the opposite of what is claimed and derives a contradiction.

IntuitionAssume the opposite, then watch it collapse

Suppose a detective wants to prove a suspect was at the scene of a crime. Instead of finding direct evidence, the detective says: "Suppose the suspect was not there. Then they could not have left this footprint, which only they could make. But the footprint is right here — contradiction. So the suspect must have been there." This is exactly the shape of proof by contradiction: to prove a statement $P$ , assume its opposite $\neg P$ , follow the logical consequences faithfully, and show they collide with something already known to be true. Since a false assumption is the only way to reach an impossible conclusion, $\neg P$ must be false, so $P$ holds.

The curve

y=x^2-2

crosses zero exactly at

x=\sqrt{2}

; the proof by contradiction below shows this crossing point can never be a ratio of two integers.

SchoolThe logical shape of a contradiction proof

Definition: Proof by contradiction

To prove a statement $P$ by contradiction, assume $\neg P$ (the opposite of $P$ ), and derive from it, using only valid logical steps and facts already established, some statement $Q$ together with its negation $\neg Q$ . Since $Q \wedge \neg Q$ is always false, the assumption $\neg P$ that led to it must be false, so $P$ is true.

\neg P \Rightarrow (Q \wedge \neg Q)

Here $P$ is the statement we want to prove, and $Q$ is any statement whose truth and falsity we can both derive from $\neg P$ — often $Q$ is a fact already known to be true (like " $\gcd(p,q)=1$ ") whose negation we accidentally derive. Once $\neg P \Rightarrow (Q \wedge \neg Q)$ is established and $Q \wedge \neg Q$ is impossible, logic forces $\neg P$ itself to be impossible, i.e. $P$ holds.

\sqrt{2} = \frac{p}{q}, \quad \gcd(p,q)=1

This second line is the concrete assumption used to open the classic proof that $\sqrt{2}$ is irrational: here $p$ and $q$ are integers with $q \neq 0$ , and requiring $\gcd(p,q)=1$ means the fraction $\frac{p}{q}$ is already written in lowest terms. The proof (given in full below) shows this assumption forces both $p$ and $q$ to be even, contradicting $\gcd(p,q)=1$ .

Comparing proof strategies
Method	Assumption	Goal
Direct proof	$P$	Derive $Q$ directly from $P$ using known facts
Contradiction	$\neg P$	Derive both $Q$ and $\neg Q$ from $\neg P$
Infinite descent	A minimal counterexample exists	Construct a strictly smaller counterexample, contradicting minimality

UndergraduateTwo classical contradiction proofs

Theorem: Irrationality of

\sqrt{2}

$\sqrt{2}$ is irrational, that is, there are no integers $p,q$ with $q \neq 0$ such that $\sqrt{2} = \frac{p}{q}$ .

Why is it true?

There is no direct algebraic way to show a number is not a ratio of integers, since that would mean checking infinitely many fractions; contradiction sidesteps this by assuming such a fraction exists in lowest terms and mining that single assumption for an impossible parity fact.

Proof

Suppose, for contradiction, that $\sqrt{2}$ is rational. Then we can write $\sqrt{2} = \frac{p}{q}$ for integers $p,q$ with $q \neq 0$ , and by cancelling common factors we may assume $\gcd(p,q)=1$ (the fraction is in lowest terms).

Squaring both sides gives $2 = \frac{p^2}{q^2}$ , so $p^2 = 2q^2$ . This means $p^2$ is even. Since the square of an odd number is odd, $p$ itself must be even; write $p = 2k$ for some integer $k$ .

Substituting back, $(2k)^2 = 2q^2$ , so $4k^2 = 2q^2$ , which simplifies to $q^2 = 2k^2$ . This means $q^2$ is even, so by the same reasoning $q$ must also be even.

But now both $p$ and $q$ are even, so $2$ divides both of them, contradicting the assumption that $\gcd(p,q)=1$ . This contradiction shows that the original assumption — that $\sqrt{2}$ can be written as $\frac{p}{q}$ — must be false. Therefore $\sqrt{2}$ is irrational.

Theorem: Euclid's proof of the infinitude of primes

There are infinitely many prime numbers.

Why is it true?

It is impossible to directly list infinitely many primes to verify the claim, so contradiction instead assumes a finite complete list exists and manufactures, from that very list, a number that exposes the list as incomplete.

Proof

Suppose, for contradiction, that there are only finitely many primes, and let $p_1, p_2, \dots, p_n$ be the complete list of all of them.

Consider the number $N = p_1 p_2 \cdots p_n + 1$ . Since $N > 1$ , it must have at least one prime divisor; call it $p$ (every integer greater than $1$ has a prime factor).

By assumption, $p_1, \dots, p_n$ is the list of all primes, so $p$ must equal $p_i$ for some $i$ . In particular, $p$ divides the product $p_1 p_2 \cdots p_n$ .

But $p$ also divides $N = p_1 p_2 \cdots p_n + 1$ . If $p$ divides both $p_1 p_2 \cdots p_n$ and $N$ , then $p$ divides their difference: $p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1$ .

No prime number can divide $1$ , since every prime is greater than $1$ . This is a contradiction. Therefore the original assumption — that there are only finitely many primes — must be false, so there are infinitely many primes.

UndergraduateReal-World Applications and Worked Examples

Proof by contradiction is a working tool far beyond competition math: computer scientists use it to prove impossibility results (no algorithm can solve the halting problem, no comparison sort beats $n\log n$ in the worst case), cryptographers rely on it to argue that breaking a scheme would imply solving a problem believed to be hard, and engineers use it to argue safety-critical impossibility claims ("if the pressure exceeded this value, the seal would have failed, but the seal is intact, so the pressure never exceeded it"). Infinite descent, a variant that assumes a minimal counterexample and shrinks it, is especially common in number theory and algorithm-termination arguments. The two examples below show contradiction and infinite descent applied to concrete combinatorics problems.

Example: The deficient chessboard: a contradiction in tiling

An $8 \times 8$ chessboard has its two opposite corner squares removed, leaving $62$ squares. Prove that this board cannot be completely covered by $31$ dominoes, each covering exactly $2$ adjacent squares.

Solution

Suppose, for contradiction, that such a tiling by $31$ dominoes exists.

Color the chessboard in the usual alternating black and white pattern, so it has $32$ black and $32$ white squares. Every domino, since it covers two adjacent squares, always covers exactly one black square and one white square (adjacent squares always have opposite colors).

Therefore, a tiling using $31$ dominoes would cover exactly $31$ black squares and $31$ white squares — $62$ squares total, split evenly by color.

However, the two opposite corners of a standard chessboard are always the same color (this is a property of the standard coloring). Removing them removes $2$ squares of one color, leaving $30$ squares of that color and $32$ squares of the other color.

This means the board actually has $30$ squares of one color and $32$ of the other, which cannot be split into $31$ -and- $31$ by any tiling. This contradicts the count from Step 3 (exactly $31$ of each color), so the assumed tiling cannot exist.

Example: Infinite descent: no nontrivial solution to $a^2=2b^2$

Use infinite descent to prove that the equation $a^2 = 2b^2$ has no solution in positive integers $a,b$ .

Solution

Suppose, for contradiction, that a positive integer solution exists. Among all positive integer solutions $(a,b)$ , choose one with $b$ as small as possible — this is possible because the positive integers are well-ordered (any nonempty set of positive integers has a smallest element).

From $a^2 = 2b^2$ , the right side is even, so $a^2$ is even, and hence $a$ itself is even (the square of an odd number is odd). Write $a = 2a_1$ for some positive integer $a_1$ .

Substituting, $(2a_1)^2 = 2b^2$ gives $4a_1^2 = 2b^2$ , so $b^2 = 2a_1^2$ . By the same reasoning as before, $b^2$ is even, so $b$ is even; write $b = 2b_1$ .

Substituting again, $2a_1^2 = (2b_1)^2 = 4b_1^2$ , so $a_1^2 = 2b_1^2$ . This means $(a_1,b_1)$ is also a positive integer solution of the same equation $a_1^2=2b_1^2$ , and since $b = 2b_1$ , we have $b_1 = b/2 < b$ .

This contradicts the choice of $(a,b)$ as the solution with smallest possible $b$ , since $(a_1,b_1)$ is a solution with an even smaller second coordinate. This contradiction shows that no positive integer solution to $a^2=2b^2$ can exist.

Proof by contradiction proves a proposition $P$ by assuming $\neg P$ and deriving a contradiction of the form:

In the classic proof that $\sqrt{2}$ is irrational, assuming $\sqrt{2} = \frac{p}{q}$ in lowest terms and squaring gives $p^2 = 2q^2$ . What is immediately concluded about $p$ ?

In Euclid's proof, assuming primes $p_1,\dots,p_n$ are all the primes, the number $N=p_1p_2\cdots p_n+1$ leads to a contradiction because:

For the deficient chessboard with two opposite corners removed, the contradiction in the domino-tiling proof arises because a tiling would need: