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 $latex P$ the aim will be to find propositions $latex A$ and $latex 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 $latex 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 $latex 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 $latex f$ from non-negative integers to non-negative integers such that $latex 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 $latex n^k$ with $latex k > 1$ can’t work. So try linear functions. And yes, $latex 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 $latex f(n) = n + 1$, and

$latex f(n) = n + 1\quad (\mathrm{for\ } n \equiv 0, 2 \mod 4)$
$latex f(n) = n + 5\quad (\mathrm{for\ } n \equiv 1 \mod 4)$
$latex 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.