Hints on Writing Mathematical Proofs

On a number of the problems on the qualifying quiz, you might be asked to "prove" something. We're more interested in how you think about a problem than your ability to write a formal proof, but it helps to know how to write down an argument and make it concrete. Thus, if you haven't worked with proofs before, we'd like to offer this guide to writing them.

Photo of Proof by Go

If you're already familiar with proofs – if, for example, you could easily prove the statement "there are infinitely many prime numbers" – then you don't need this guide. If not, though, it will help us to understand your thought processes if you know how to write about them, and it will help you know when you're done with a problem to know how much detail we'd like to see.

Suppose you're given a problem like this one, taken from the 2002 qualifying quiz:

Show that you cannot cover a circular disk with two circular disks of smaller diameter.

Just showing us a picture of a big circle with two smaller ones not quite covering it isn't sufficient: you've only shown one case. There are infinitely many ways to try to cover one disk with two others, so we need some way to deal with all infinitely many cases.

What we'll do is show that, no matter how you lay down the two disks, they don't cover the bigger one. This actually isn't so hard. Call the big disk C, and the smaller disks A and B. Let's look at the border circle of C, its circumference. Each of A and B will cover an arc of that circumference, but each arc will have length less than half the circumference of C: if it had length equal to half the circumference or more, then it would contain two points on opposite sides of C. Those two points would be as far apart as the diameter of C, which is too far apart for both to be contained in just one smaller disk.

Since each disk covers less than half the circumference of C, together they can cover a length of circumference at most the sum of the arcs they each cover, which is not enough to cover all of the border of C. Thus, laying them down does not cover all of C.

Suppose instead you're given a problem like this one, taken from the 2003 qualifying quiz:

There are several cities in a certain kingdom. An obnoxious citizen is exiled from city A to city B, which is the furthest city in the kingdom from A. After a while, he is exiled from city B to the furthest city from it, which happens to be different from A. Prove that, if his exiles continue in the same way, he will never return to city A. You may assume that the distances between cities are all different.

Although this statement seems complicated, it's not actually that hard to prove. First, we make the observation that, if the citizen is exiled from some city X to another city Y, and then to Z, the distance from X to Y (we'll write it XY) is less than or equal to the distance YZ, that is, XY ≤ YZ. So, if he's exiled from A to B, then to C, then to D, and so on, we have:

AB ≤ BC ≤ CD ≤ ... (1)

Since A is different from C, we know that AB ≤ BC, and they are not equal; we can change (1) to read:

AB < BC ≤ CD ≤ ... (2)

which is different only because the first inequality is now strict.

Now suppose that he gets exiled back to city A at some point, from some city N. Then the distance NA appears in the inequality (1), and so it must be greater than or equal to anything that comes to the left of it. AB is the first distance in the inequality, and so NA is greater than AB (and not equal). But then the distance from N to A is greater than the distance from A to B, which is a contradiction because the citizen was first exiled to B, the farthest city from A. Thus, N cannot be farther from A than B; so the citizen can not be exiled back to A from N, or any other city.

Finally, we'll give you one of the classic results of mathematics. A prime number, as you're probably aware, is a number that has no divisors other than 1 and itself. There are infinitely many prime numbers: 2, 3, 5, 7, 11, and so on. This is a mathematical theorem that has been proven.

Suppose that it was not true; that there were only finitely many prime numbers. If this was the case, we could label them p1, p2, ..., pn, and this could be a list of all the prime numbers (e.g. p1 = 2, p2 = 3, p3 = 5, and so on).

If we multiply them all together to get p1p2p3...pn, then this number is divisible by all the prime numbers. Now add one to it: p1p2p3...pn + 1. This number is not divisible by any prime number.

But any number has a prime factorization, so if we take the prime factorization of p1p2p3...pn + 1, we get some new prime number that divides it. This prime number was not on our list, but our list was supposed to have all prime numbers. Thus, our list could not exist, for any list would always be missing a prime number: we could always construct some new one!

If you've understood all these writeups, then you're ready to tackle the quiz. However, if you think you need more guidance, or if you'd like to read more about proofs, here are a couple of other web pages we can recommend:

Happy proving!