Be smart by being systematic?

I’ve just got this notice of tomorrow’s Trinity Maths Society meeting (details of when/where at that link, if you are in Cambridge). Sounds as if it should be fascinating …

Prof Tim Gowers FRS (DPMMS):
“Can interesting mathematics problems be solved systematically?”

Solving a mathematics problem that is not a routine exercise can often  feel more like an art than a science. Different people attack problems  in different ways, and ideas can appear to spring into one’s mind from  nowhere.

I shall argue that solving problems is a much more systematic
process than it appears, and shall also try to explain why, if that is  the case, it has the features that make us think that it isn’t. For the  bulk of the talk, I shall attempt, with help from the audience, to solve  an Olympiad-style problem that I have not seen before, and to do so  systematically rather than by waiting for a clever idea to appear out of  the blue. The attempt is not guaranteed to succeed, but I hope that it  will be informative whether or not it does.

Perhaps, in the spirit of the times, someone should try live-blogging as the clock ticks down through the meeting! I’m not sure I’ll be able to get there — but if I can, I’ll try to take notes good enough to report back, as Tim Gowers can be fascinating on this kind of topic.

[Added 27th January] Well, I did go the meeting which was fun but actually not that illuminating. In so far as Tim Gowers had suggestions about how to approach problems “systematically”, they were rather anodyne rules-of-thumb for trying to find easier things to prove which together might give you (or point the way to) what you want. Thus sometimes if you want to prove a target result P the aim will be to find propositions A and A \Rightarrow P which look easier to prove –“easier” relative to your background knowledge, of course. Sometimes a good bet will be to try to prove a special case of the general proposition P, for the proof of the special case may reveal rather naturally what needs to be done to generalize. Sometimes the thing to do will be to prove a more general proposition P' (it may be easier to find a proof of the more general proposition because there are fewer ideas in play, cutting down the routes it seems natural to explore). Sometimes fiddling around with the terms of the problem, unpacking definitions etc., may simplify things by allowing you to hit the problem with what you already know.

All true — and Tim Gowers indicated some examples — but advice along the lines of “try breaking down the proof-goal to simpler-for-you sub-goals” is not exactly a systematic heuristic!

In the second part of talk, the audience were offered a list of Olympiad-style problems which Tim Gowers promised he’d not worked on before. I think these were proposed Olympiad questions rather than actual questions, so I’m not sure what kind of check there would be at this stage on difficulty-level. Anyway, the one chosen to tackle was this:

Find all the functions f from non-negative integers to non-negative integers such that f(f(f(n))) = f(n + 1) + 1.

A not unfamiliar type of such question. So how are we do approach this systematically? And what’s the solution we thereby reach?

First question: are there any solutions at all? (that seems pretty natural to begin with). Try polynomials. It’s obvious that a polynomial with leading term of order n^k with k > 1 can’t work. So try linear functions. And yes, f(n) = n+ 1 does the trick.

So we’ve got one solution. Are there others?

Well, at the time of writing this, I don’t know! After half-an-hour, Tim Gowers hadn’t found it (and an audience of maybe 400 — with quite a few recent Olympiad participants, I guess — hadn’t been able to help him out). Some not-very-systematic probings left us still floundering.

When the usual closing time for meetings arrived, the TMS President declared that extra time would be played after a ten minute break. But I had to leave the meeting, so I don’t know if the answer was found. I’ll let you know if I ever discover it. But the promised illustration of a successfully systematic approach to tackling such a problem didn’t come off. (So enormous credit to Tim Gowers for putting himself on the line like this!)

[Added later, 27 Jan.] You can find two full solutions at pp. 16-17 here. The headline is that the there are just two functions satisfying the condition, namely f(n) = n + 1, and

f(n) = n + 1\quad (\mathrm{for\ } n \equiv 0, 2 \mod 4)
f(n) = n + 5\quad (\mathrm{for\ } n \equiv 1 \mod 4)
f(n) = n - 3\quad (\mathrm{for\ } n \equiv 3 \mod 4)

But, the difficult bit, to show these are the only solutions without magic (or a “clever idea out of the blue”) — especially in Olympiad conditions — will surely require that you have up your sleeve a repertoire of known techniques and approaches for this sort of problem, and a practiced sense of what is likely to work. And it is interesting that some ingredients used in the solutions were suggested by students in the TMS audience apparently familiar with this general kind of question.

This entry was posted in This and that. Bookmark the permalink.

6 Responses to Be smart by being systematic?

  1. Rowsety Moid says:

    Is “an Olympiad-style problem” an interesting problem, in the relevant sense of “interesting”? I’m inclined to think it isn’t.

  2. Anthony Wagstaff says:

    Very interested to hear what he’s arguing here. He does say “solving problems is […] much more systematic” rather than “entirely systematic”; so he’s saying they can’t be solved entirely by a machine, perhaps? And I don’t think anyone would say it is “entirely unsystematic”. So what is this “much more”?

    Rather serendipitous your blog arrives in my email just as I’m reaching the end of an interesting paper concerned, in part, with Turing’s “universal computing machine”, and Gödel of course – Wittgenstein, Turing, and the “Finitude” of Language by Paul Livingston.
    Is arriving at a system with which to solve maths problems, itself systematic? Is it a discovery, or a creation, I wonder?

  3. Alex R says:

    I very much agree mathematics (that is, proving theorems and constructing new fields) is more of an art than a science at a high-level. Certainly, doing it well and in a way other mathematicians can understand, is certainly no simple mechanism!

    This reminds me also of Pólya’s excellent booklet “How to Solve It”, which expounds various approaches and heuristics to mathematical problems and proofs. It’s no panacea of course, but many a budding mathematician can grown (and has grown) greatly from this.

  4. David Auerbach says:

    I think Gowers intends ‘systematically’ to include a fair amount more than ‘here’s a procedure’ (although less than ‘I’ll take trolley ride and see what strikes me.’) It might just be more up-to-date focused heuristics as in Pólya. As to “interesting”, I’m inclined to charity here. He wants a chance of doing it in the time allotted and this would serve as a sort of proof of concept.

    • Rowsety Moid says:

      I take the point about time, and I think it’s an interesting experiment. (I’m certainly interested in hearing what sort of approach he took.) But I don’t think an Olympiad-style problem is a good enough test for the idea that interesting mathematics problems can be solved systematically. If someone told me that solving Olympiad-style problems ” is a much more systematic process than it appears”, then I wouldn’t find that as surprising or interesting a claim as one about “interesting mathematics problems” more generally.

Leave a Reply

Your email address will not be published. Required fields are marked *