Resources

Visit the AoPS Book Store.

How to Write a Solution
Name Your Characters
by Mathew Crawford & Richard Rusczyk

A large thin-shelled vehicle for a young fowl that was created by a huge female bird sat on a wall. The large thin-shelled vehicle for a young fowl that was created by a huge female bird had a great fall. All the horses of the great man who lived in a large castle that ruled over the people in the land and all the men of the great man who lived in a large castle that ruled over the people in the land couldn't put the large thin-shelled vehicle for a young fowl that was created by a huge female bird back together again.

Proofs are a lot like stories. When writing a solution your job is tell a math story in a way your audience will understand and enjoy. Instead of writing about 'A large thin-shelled vehicle for a young fowl that was created by a huge female bird,' we call that big egg 'Humpty-Dumpty' and tell the story. Likewise, a well-written proof often involves naming the important quantities or ideas that play a part in the story of your solution. Naming your characters can also help you find solutions to problems, so it's not something you should wait until proof-writing time to do.

When you do name your characters, you name them simply, clearly, and write up front, so the reader knows exactly where to go to find out exactly who this n person is and what that f(x) function stands for.

Here's an example problem:

Problem: Show that for any set of 100 integers that there is some subset such that the sum of its elements is a multiple of 100.

The solution below is hard to read because the integers and the sums that are the key to the solution remain unnamed.

How Not to Write the Solution:
Suppose we put the numbers in our set in some fixed order. If we start from the beginning, there are 100 sums we can make by just adding up starting from the beginning number. We could add up the first 2 numbers, or the first 4, the first 57, or whatever. If one of these sums is a multiple of 100, then we are done. If none of the sums is a mutliple of 100, then there consider the remainders when each of these terms is divided 100. There are 100 total remainders since there are 100 sums. Since none of them is 0, there are at most 99 different remainders among these 100 remainders. Therefore, two of these remainders must be the same since if there weren't at least two the same there could only be 99 total remainders (since we know none is zero). Now, take the difference between the two sums which have the same remainder when divided by 100. This difference must have a remainder of 0 when divided by 100. Suppose we have subtracted the sum with fewer numbers from the one with more numbers. When we take this difference, all the numbers in the second sum cancel with numbers in the first sum, because each sum is just adding up numbers in our set starting with the first one but the second sum is shorter. Due to this cancellation, the difference of these two sums which have the same remainder when divided by 100 results in a sum of numbers in the original set. We have shown that this difference has a remainder of 0 when divided by 100, so this is our desired sum of numbers in the set that is divisible by 100.

The solution below is easy to read because the main characters have names. Specifically, we name the integers in the set and the sums of the elements in subsets that we examine. These names allow us to follow the characters throughout the story. They also allow the writer to describe the characters more completely and succintly.

How to Write the Solution:

Call the 100 integers n1, n2,..., n100.

Let Sk = n1 + n2 + ... + nk for k = 1, 2,..., 100.

Case 1: If S1, S2,..., S100 are all distinct (mod 100), then exactly one of them must be a multiple of 100.

Case 2: Otherwise, the 100 sums, Sk, have at most 99 distinct residues (mod 100) and by the Pigeonhole principle two of the sums, Sk, have the same residue (mod 100).

This means there exist some integers j and k, 0 < j < k < 101, such that

Sk Sj (mod 100);
thus,

Sk - Sj 0 (mod 100).

Now, consider the subset with elements nj+1, nj+2,..., nk. The sum of the elements of this subset is

nj+1 + nj+2 + ...+ nk = (n1 + n2 + ... + nk) - (n1 + n2 + ... + nj)

= Sk - Sj 0 (mod 100).

Thus this sum is a multiple of 100 and we are done.

Previous Section: sdrawkcaB knihT, Write Forwards
Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • FoundationPrivacyContact Us