The Art of Mathematical Problem Solving
I still remember the day in seventh grade when, alone in the classroom, I found the geometry problems section in the appendix of one of our books and started to work them out, tentatively at first, but increasingly confidently as they started falling into place. Joyfully too -- bitten by the bug and still infected after all these years. The problem notebooks become buried under files with more pressing business, always to be brought back to the top after a time to receive another solution.
The preoccupation can become an ongoing part of your psyche. Ramanujan used to say that a Hindu goddess came to him in dreams with his formulas and he would write them down first thing in the morning. Poincaré has a story (as I remember it) that he had hit a stone wall on a problem after considerable application. He decided he needed a break and took a trip to the country by bus. When disembarking, as his foot rose from the last step and before it fell on the ground, the solution came to him. I was waiting for a friend at a bar once and drew a diagram of a geometry problem I'd been working on unsuccessfully on a napkin, not even applying myself, just doodling absent-mindedly, when the solution revealed itself.
It's like reading, with different kinds of problems suiting different moods. Some require machinery and a new line of thinking; some are knock-offs from first principles, but fun because of novelty or unexpected associations (Mathematics Magazine used to have a section called "Quickies"). This is virtually a branch of Mathematics today and the amount of resources is astounding -- sources for problems and solutions and strategies. Here are examples of each kind:
1) Prove that tan ((tan-14) / 4) = 2 (cos(6π/17) + cos(10π/17)) (Mathematics Magazine, Problem #1562, December 1998).
2) Without any overt calculations, find the five adjacent natural numbers whose product most closely approximates 1,000,000 (from friend JB). Warning -- spoiler at end of the next paragraph.
The first one was almost a joke at first, ridiculously inaccessible, but it made an impression for some reason, I suppose because of the bizarre appearance of 17. Then some time later (years) I read Ian Stewart about the construction of the regular 17-gon, which is the culmination of Gauss's Disquisitiones Arithmeticae, highly accessible itself, with some effort (Galois Theory, 2nd ed., by Ian Stewart, §17.4 at pp 170 - 174). Stewart, in a proof based on Hardy and Wright, employed the 17th roots of unity ekiθ, 0 ≤ k ≤ 16, where θ = 2π/17. Not only that, but cot(4φ) made an appearance, for some angle φ. The proof almost writes itself! Put the book away and have at it, retracing the steps of the great one and getting a feel for that episode of math history as well as experiencing all the usual pleasures - solution here (large pdf). Spoiler for second problem: the key is remembering that 1,000,000 ~ 220.
The problem-solving phenomenon has been quickened by the International Mathematical Olympiad (IMO), an international competition for students just finishing high school. The model was established in Hungary in 1894 with the Eötvös Competition. The link contains the problems over the years and solutions can be found in books from the New Mathematical Library. Incidentally, the key to benefiting from such books is never, never to look at the solution until after solving the problem yourself. And then cover adjacent problems, no peeking! All these competitions get harder over the years as coached prep teams become more and more adept and the problems advance to match their expertise. Don't get too cocky if 1894 is a breeze - 1920 will give you something to think about and 1995 might be impenetrable. There were three problems every year; here is 1928/1:
Prove that, among the positive numbers a, 2a, ..., (n - 1)a, there is one that differs from an integer by at most 1/n.
Here is my solution, and here is the one in NML.
Hungary made an outsize contribution to world mathematics in the early twentieth century (think the Riesz brothers, Polya, and von Neumann, among others). The competitions were designed to identify and nurture young mathematical talent, and leading Hungarian mathematicians worked with high school teachers to administer the tests, but also prepare young people for them.
Wikipedia rightly calls the IMO the "pinnacle of mathematical competition among high school students". (August 2013) It started in 1959 in the Soviet bloc and gradually spread to other countries, one hundred or so now participating. Each country sends up to six contestants and each attempts to answer six questions over two days, four and a half hours per day. NML has published International Mathematical Olympiads 1959-1977, compiled and with solutions by Samuel Greitzer. Problems became notably harder over that period and are just about impossible today without serious preparation. Problems are "elementary" in that they don't require calculus or advanced machinery not part of the high school curriculum (group theory, for example), but of course assume considerable knowledge, including elementary theorems in number theory, combinatorics, geometry, trigonometry, inequalities, and similar subjects. There is quite an art in coming up with such problems and of course the problem solvers' coaches are one and the same with the problem posers. Past IMO problems can be found at the official site and many countries have their own competitions feeding into IMO - for example, the USA Mathematical Olympiad, past problems here.
My high point as an Olympian was solving 1977/1 (large pdf), Greitzer's solutions here:
Equilateral triangles ABK, BCL, CDM, DAN are constructed inside the square ABCD. Prove that the midpoints of the four segments KL, LM, MN, NK and the midpoints of the eight segments AK, BK, BL, CL, CM, DM, DN, AN are the twelve vertices of a regular dodecagon.
Many books today help would-be problem solvers grasp the rudiments of this art. There's a fine line, because there are definitely tricks of the trade and a foundation of theorems and methods to be mastered, but the whole point is to foster ingenuity and non-standard approaches. One of my favorites is Loren Larson's Problem-Solving Through Problems from Springer-Verlag. Professor Larson was problems editor for Mathematics Magazine for years and knows whereof he speaks. The book is divided into topical chapters (induction and pigeonhole principle, arithmetic, inequalities, etc.), each in turn broken into sections concerning a given concept, method or theorem (for arithmetic: greatest common divisor, modular arithmetic, arithmetic of complex numbers, and so on). Each section starts with a short exposition, quickly giving way to a few worked problems, followed by still more unworked problems. Citations are given for many of the problems (1975 IMO, for example, or journal number).
Mathematics Magazine has a problems section where, in days past, you would mail in a solution ahead of the deadline, then some time after that, a solution would be chosen for publication and others with correct solutions credited. I got a number of credits, but no solutions published. I would always type them up as nicely and you learn what a royal pain even simple mathematical typesetting is. Here is the solution to Problem 1456 (October 1994):
Show that the only sequence of numbers (αi) that satisfies the conditions
(i) αi > 0 for all i ≥ 1, and
(ii) αi-1 = (iαi + 1) / (αi + i) for all i > 0,
is the sequence αi = 1 for all i.
Typesetting this devil took longer than solving it - it might have been a TeX exercise, I forget, but stopped typesetting solutions because it quickly turned something fun into something beyond drudgery.
There are problems I've worked on intermittently for years, some never yielding, others finally giving way. It's deflating to finally solve (or think you've solved) a problem, then turn to the three line solution in the back of the book. That too is grist for the mill - you're not going to forget that trick soon. A real delight is to encounter a new method late in the day, unknown through all those earlier years and the two Math degrees. An example is the method of invariants through basic Euclidean plane transforms (mirror, translate, rotate). Professor Dan Pedoe unlocks the door of this one in his book Geometry: A Comprehensive Course, published in a cheap reprint by the estimable Dover Publications (see Chapter II: Circles, and Chapter V: Mappings of the Euclidean Plane). Here is the kind of problem you can solve with this method and here is how to solve it:
Given a point P in the plane, construct an equilateral triangle whose vertices are 1, 2, and 3 units, respectively, from P.
Some problems lend themselves to computer investigation. And some don't - Donald Knuth was good at posing problems looking like the first kind that were actually the second, as you would expect from someone bridging Mathematics and Computer Science (see his Concrete Mathematics). Plotting 1000 random points in a geometric simulation can produce counter-examples or suggest plausible hypotheses. A great older book in this vein is Exploring Mathematics with your Computer, by Arthur Engel - it may be from 1993 and use Turbo Pascal (!), but lucidly analyses the kinds of problems amenable to computer methods (and super cheap today). Take this one from the University of Wisconsin - Madison Mathematics Talent Search (November 2009, Problem Set II):
Show that the equation a2 + b2 = c2 + 5 has infinitely many positive integer solutions.
A simple PHP program produces many triplets for low values of (a, b, c), which in turn reveal patterns provable in all generality. Depending on taste, we can erase all trace of the computer hinting or not. Write-up here, including the suggestive output from the computer program.
Here's another from The Bent Magazine, Summer 1990 (Tau Beta Pi Engineering Honor Society):
What is the smallest prime number that contains each of the 10 digits 0 to 9 at least once?
Basic analysis gets you to 120 different possibilities, then a C program examines them systematically. It's a longish program, but includes standard routines to calculate permutations and determine primality. No doubt the sieving could be done reasonably efficiently with paper and pencil as well, but writing the correct C program is problem solving too, and a pleasant form of it for some of us. The solution is here.
Mike Bertrand
August 10, 2013