What makes a mathematical proof “elegant”?

Answer by Ray Li:

I will illustrate with one of my favorite problems.

Problem: There are 100 very small ants at distinct locations on a 1 dimensional meter stick. Each one walks towards one end of the stick, independently chosen, at 1 cm/s. If two ants bump into each other, both immediately reverse direction and start walking the other way at the same speed. If an ant reaches the end of the meter stick, it falls off. Prove that all the ants will always eventually fall off the stick.

Now the solutions. When I show this problem to other students, pretty much all of them come up with some form of the first one fairly quickly.

Solution 1: If the left-most ant is facing left, it will clearly fall off the left end. Otherwise, it will either fall off the right end or bounce off an ant in the middle and then fall off the left end. So now we have shown at least one ant falls off. But by the same reasoning another ant will fall off, and another, and so on, until they all fall off.

Solution 2: Use symmetry: Imagine that the ants walk through each other rather than bump off each other. If we view the ants as indistinguishable, this is the same problem, so they all just walk off the meter stick.

So to answer the question,

1) An elegant proof is unexpectedly simple.

The first solution is fairly intuitive. It could be formalized a bit, but it's essentially correct. However, it's easy to be satisfied with that solution, dismiss the problem for being too boring or uninsightful or whatever, and not anticipate that there is a slicker solution. 

2) An elegant proof hits at the heart of the problem's complexity

The problem gives us a very straightforward setup, and wants us to go from that to a bunch of dead ants. Clearly, this would be very easy if it weren't for the sentence, "If two ants bump into each other, both immediately reverse direction and start walking the other way at the same speed." This condition is the hardest part of the problem, but the key observation in the second solution eliminates it in one shot.

3) An elegant proof reveals more about the subject than simply its result.

The second solution allows us to answer many more questions about the problem's context beyond the problem statement. For example, "What is the longest possible time until all the ants fall off?" With the reasoning in the first solution, this seems pretty impossible, but from the second, we note that because the ants essentially walk by each other, the longest time is just [math]\frac{1 m}{1 cm/s} = 100 s.[/math] For fun, you also can ask yourself questions like, "Suppose the meter stick were bent in a circle, so now the ants just keep walking instead of falling off. Also suppose the ants are distinguishable. What's the longest possible time until the first instance that every ant has returned to its original position?" The beauty of math lies in the connections you can draw between seemingly separate concepts and ideas, and an elegant proof highlights this beauty as well as proving the result.

What makes a mathematical proof "elegant"?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s