Problem-Solving Lessons From George Pólya

I was lucky enough to see Derren Brown's latest show, Infamous, during my London trip this summer. For those of you who might not be familiar with him, he is a British illusionist, mentalist and skeptic. While the show left the audience in great awe, I for the most part, was left with a deep curiosity of figuring out how he did the tricks and illusions. I would catch myself still pondering how he might have pulled the last trick only to realize I was about to miss the beginning of the next. In some ways, a mathematical theorem is not so different from a magic trick. Consider, as an example, the extraordinary theorem expressed by Euler's identity eiπ+1=0e^{i \pi} + 1 = 0 . It is hard to look at this result and not be amazed by its depth and simplicity. And yet, similar to the magic trick, the feeling immediately following awe upon reading such a result is curiosity about how the result was discovered and proved.

The process of mathematical discovery and proof is one that is fascinating from both a psychological perspective and a practical one. Recently I read Newman's selections from Pólya's influential book How to Solve It and decided to write a short post here about it. The book itself is now on my long "to read" list. All quoted text in this post is from Pólya's How to Solve It.

Yes, the solution seems to work, it appears to be correct. But how is it possible to invent such a solution? Yes, the experiment seems to work, this appears to be fact; but how can people discover such facts? And how could I invent or discover such things by myself?

Induction

The first part is Pólya's introduction to induction as a process of mathematical discovery and proof. His introduction is different from the typical "textbook" introduction to induction in that it goes over the whole process and not just the last step which is a formal proof technique. The full process is in fact a process very similar to induction as is used in the natural sciences. It consists of noticing patterns, experimenting further to see if the observed patterns repeat, making the observed patterns more specific if possible, and finally using the formal tool called "mathematical induction" to prove the observed pattern always holds. Only the last step is different in mathematics, given that the natural scientist does not have, in Pólya's words, the "higher authority" that is mathematical proof.

Pólya's first example starts by noticing, perhaps by chance or experimentation, that 1+8+27+64=1001+8+27+64 = 100 . Observing that might lead us to theorize that perhaps the sum of cubes is always a perfect square. At this point, we have very little evidence for such a claim, so we proceed to test this further by trying 1+8=9=321+8 = 9 = 3^2 , 1+8+27=36=621 + 8 + 27 = 36 = 6^2 and 1+8+27+64+125=225=1521 + 8 + 27 + 64 + 125 = 225 = 15^2 , and seeing that the initial guess holds. At this point, it seems unlikely (though entirely possible) that this is a mere coincidence. The astute observer can then deduce an even more interesting pattern here by observing the sequence of perfect squares as 1,3,6,10,151, 3, 6, 10, 15 , suggesting that they are of the form n(n+1)2\frac{n(n+1)}{2} . With this, we can come up with a very specific conjecture:

i=1ni3=(n(n+1)2)2 \sum_{i=1}^{n}i^3 = \left(\frac{n(n+1)}{2} \right)^2 \cdot

We can then proceed to prove this conjecture by using the proof technique known as mathematical induction. The technique consists of proving the hypothesis holds for a base case, and then showing that if it holds for some nn , then it holds for n+1n+1 . The technique is taught early on in discrete mathematics and as such I will not go into it here. What I found much more interesting about Pólya's treatment of induction was his emphasis on the earlier parts of the process, which matter much more while doing mathematical research or problem solving, rather than solving already-solved exercises. Pólya even goes to say that the name for the proof technique is "unfortunate", suggesting perhaps a better name would be "proof from nn to n+1n+1 " or "passage to the next integer." Finally, Pólya discusses how in making the conjecture more precise, that is, in going from stating that such sums are squares to the more specific statement saying that they are precisely of the form (n(n+1)2)2\left(\frac{n(n+1)}{2} \right)^2 , we made the proof much easier. This might seem paradoxical but is often the case in mathematics--the stronger the claim, the easier the proof.

Mathematics presented with rigor is a systematic deductive science, but mathematics in the making is an experimental inductive science.

Setting Up Equations

Newton compares setting up mathematical equations for a problem to translating from one language to another in Arithmetica Universalis. Pólya expands on this comparison and provides a few examples, showing how such translations are straight-forward for simpler cases and become increasingly more difficult as more technical terms and more implicit understanding of the problem is required, somewhat akin to translating a text full of idioms from one language into another.

Pólya's first example is the following problem:

Find two quantities whose sum is 78 and whose product is 1296.

He then proceeds to provide a side by side translation like this:

In English In Algebraic Language
Find two quantities xx , yy
whose sum is 76 and x+y=76x+y=76
whose product is 1296 xy=1296xy=1296

This is an example of a straight-forward translation. His next example is a bit more complicated and involves knowing the formulas for the surface area and the volume of a prism. His last example comes from analytic geometry and goes:

Given the equation of a straight line and the coordinates of a point, find the point that is symmetric to the point with respect to the given line.

To translate this problem into equations, we need to understand quite a bit of analytic geometry. We need to know what an equation of a line looks like and what being symmetric with respect to a straight line means and how it is expressed in equations. And furthermore, we have many different ways of expressing the same thing using equations. For example, a straight line can be expressed using a slope and a point, or two points, or a vector and a point. Similarly, being symmetric can be expressed in various ways. This is akin to the translators choices for certain words or idioms. Picking the right one can make understanding and solving the problem much easier. The following is Pólya's translation.

In English In Algebraic Language
The given point (a,b)(a,b)
and the point required (p,q)(p,q)
are so related that first the line joining them is perpendicular to the given line and qbpa=1m\frac{q-b}{p-a}=-\frac{1}{m}
second, they lie on oppose sides of the given line but are at equal distance from it. bman1+m2=qmpn1+m2\frac{b-ma-n}{\sqrt{1+m^2}} = -\frac{q-mp-n}{\sqrt{1+m^2}}

His translation is beautiful in its simplicity and in the way in which the equation asserting symmetry is symmetric itself. I will be trying this method of side by side translation next time I have to teach a word problem, such as optimizations, to students.

The Traditional Mathematics Professor

This section is Pólya's short take on the traditional mathematics professor and is more humorous than anything. He does bring up a valid point though: that you can still learn from such teachers.

He prefers to face the blackboard and turn his back on the class. He writes a, he says b, he means c; it should be d. [...] After all, you can learn something from this traditional mathematics teacher. Let us hope that the mathematics teacher from whom you can not learn anything does not become traditional.

Working Backwards

Our usual approach to problem solving is a direct one. We start from the premises and try to reach the conclusion. This approach often works for simple problems. With some problems however, the direct approach takes us on too many detours before getting us to the destination, and that's if it gets us there at all. Consider the following example discussed by Pólya.

How can you bring up from the river exactly six quarts of water when you have only two containers, a four quart pail and nine quart pail, to measure with?

The direct approach to this would be to start filling the containers, emptying them into each other, and trying various combinations of this until, by chance, you come upon the solution. This method, apart from taking a possibly long time, has the disadvantage of being very unsatisfying. Rather than feeling like you constructed the solution, you can not help but feel like you merely stumbled upon the solution by luck. And after all, who can brag about winning the lottery?

Instead, let's start from the destination and work backwards. Assume that we have six quarts in the 9-quart container. We could have gotten to this state by having had nine quarts in it and having poured out exactly three. We could have done this if the 4-quart container had one quart in it. So we reduced the problem to that of having exactly one quart in one of the containers. This latter problem has an easier solution: fill the 9-quart container and pour the contents into the 4-quart container twice, leaving one quart in the 9-quart container. We are done, as all we have to do is retrace our steps in the opposite order.

This approach, although not very natural at first, can be a powerful problem-solving technique.

We concentrate upon the desired end, we visualize the final position in which we would like to be. From what foregoing position could be get there? It is a natural question to ask and in doing so we work backwards.

Source

This post is based on How to Solve It as published in James R. Newman's World of Mathametics, volume 3.

Comments