05 Proof by contradiction

Some of the most famous proofs in mathematics,

  1. that the square root of 2 is irrational,
  2. that there are infinitely many prime numbers, and
  3. that the real numbers are uncountable (too dense to be listable in an order),

are constructed by contradiction and are accessible from school mathematics. It is often seen that a direct proof promises to look very complicated and these are the occasions to try contradiction.

The method is based on a simple, maybe subtle idea, that if we assume the result to be false, and gain a contradiction, we have proved the desired result. In logic, if proposition A implies proposition B, then the contrapositive of this statement is true, i.e. if proposition B is false, then so is proposition A. For example if I live in Canberra then I live in Australia. The contrapositive of this statement is if I don't live in Canberra then I don't live in Canberra, which is a logically equivalent statement.

The following problem, taken from the International Mathematics Tournament of Towns, is most easily solved by contradiction.

Example 5.1

There are 2000 apples, contained in several baskets. One can remove baskets and/or remove any number of apples from any number of baskets. Prove that it is possible to have an equal number of apples in each of the remaining baskets, with the total number of apples being at least 100.

Strategy

This is hardly in the form that a student might encounter at school, and the initial challenge is to figure out what is being asked. The indeterminacy of the situation and the variety of possibilities for removal of apples and baskets boggles the mind. An efficient way to control the situation is to suppose that the result is false. As the reader will see in the solution, it is not so difficult in this direction to find a contradiction.

Solution 5.1

Suppose that we have a configuration of apples and baskets for which the result fails to hold. It does not change the problem if we assume that all empty baskets have initially been removed. Then the number of remaining baskets does not exceed 99; otherwise, we could leave an apple in each basket and get a contradiction.

In a similar way, we see that number of baskets with at least two apples cannot exceed 49; the number of baskets with at least three apples cannot exceed 33, and so on. We now estimate the number of apples in the baskets. This cannot exceed

99 + 49 + 33 + 24 + …. < 100(1 + 1⁄2 + 1⁄3 + 1⁄4 + … + 1⁄99) < 100(1 + 1⁄2 + 1⁄2 + 1⁄4 + … + 1⁄64) < 100(7) = 700.

However, this contradicts the assumption that there are at least 2000 apples.