The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out last Wednesday, reads as follows:
Problem 6. Let be distinct positive integers and let be a set of positive integers not containing . A grasshopper is to jump along the real axis, starting at the point and making jumps to the right with lengths in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in .
Of the 500-odd participants in the Olympiad, only a half-dozen or so managed to solve this problem completely (I don’t have precise statistics yet). I myself worked it out about seven hours after first hearing about the problem, though I was preoccupied with other things for most of that time period.
I thought that this problem might make a nice “mini-Polymath” project to be solved collaboratively; it is significantly simpler than an unsolved research problem (in particular, being an IMO problem, it is already known that there is a solution, which uses only elementary methods), and the problem is receptive to the incremental, one-trivial-observation-at-a-time polymath approach. So I would like to invite people to try solving the problem collaboratively on this blog, by posting one’s own comments, thoughts, and partial progress on the problem here.
To keep with the spirit of the polymath approach, I would however like to impose some ground rules:
- Everyone who does not already know the solution, and has not worked on the problem already, is welcome to jump in and participate, regardless of mathematical level.
- However, in order not to spoil the experiment, I would ask that those of you who have already found a solution not to give any hint of the solution here until after the collaborative effort has found its solution. (At that point, everyone is welcome to give out their solutions here.) For instance, I will not be participating in the project except as a moderator.
- For similar reasons, I would ask that competitors at the actual 2009 IMO refrain from commenting substantively on the problem on this thread until after the collaborative effort has succeeded. (I know this may require some significant restraint, but I suspect the problem will become too easy if we get comments along the lines of “This was a tough problem! I tried X and Y and Z, and they didn’t work; I tried W also but ran out of time. I hear that someone solved the problem using U, though.” Of course, after the collaborative effort has succeeded, you are more than welcome to share your own experiences with the problem.)
- Participants should avoid explicitly searching for solutions to this problem on the internet (I would imagine spoilers would become available in a few days). If you do accidentally find such a solution online, I would ask that you recuse yourself from the rest of the collaboration, until after they have found a solution also. (In particular, posting links to a solution is strongly discouraged until after the collaborative effort has succeeded.)
- In a similar vein, extensive searching of the mathematical literature should only be undertaken if there is a consensus to do so on this thread.
- Participants are also discouraged from working too hard on this problem “offline”; if you have a potentially useful observation, one should share it with the other collaborators here, rather than develop it further in private, unless it is “obvious” how to carry the observation further.
- Actually, even “frivolous” observations can (and should) be posted on this thread, if there is even a small chance that some other participant may be able to find it helpful for solving the problem.
- Similarly, “failed” attempts at a solution are also worth posting; another participant may be able to salvage the argument, or else the failure can be used as a data point to eliminate some approaches to the problem, and to isolate more promising ones.
- Participants should view themselves as contributing to a team effort, rather than competing with each other (in contrast to the actual IMO). The point is not to obtain bragging rights for being the first or quickest to solve the problem (which has, after all, already been solved), but instead to experimentally test the hypothesis that a mathematical problem can be solved by a massive collaboration, without requiring serious effort on behalf of any one of the participants. (See Tim Gowers’ essay “is massively collaborative mathematics possible?” for more discussion.)
- To make it easier to reference comments in this thread, I would ask commenters to number their comments (so that the first comment be labeled 1., the second comment be labeled 2., and so forth.)
- Unlike the actual IMO, there is no artificial time limit on this exercise, though if there is insufficient participation, or the collaborative effort grinds to a halt, I may at my discretion close the experiment and give out solutions after a reasonable time period.