IMO 2009 Q6 as a mini-polymath project

20 July, 2009 in math.CO, polymath, question | Tags: international mathematical olympiad, mini-polymath1 | by Terence Tao

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 $a_1, a_2, \ldots, a_n$ be distinct positive integers and let $M$ be a set of $n-1$ positive integers not containing $s = a_1 +a_2 +\ldots+a_n$ . A grasshopper is to jump along the real axis, starting at the point $0$ and making $n$ jumps to the right with lengths $a_1, a_2, \ldots , a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $M$ .

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.
1. 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.
2. 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.)
1. 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.
1. 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.
2. 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.

184 comments

21 July, 2009 at 5:35 am

jens

140. to 139
oh yes, I see the problem, thanks

21 July, 2009 at 7:14 am

David Escott

141. I’m suspicious that Terry is removing posts which give away too much of the answer/have working proofs. So I’m putting my observations from earlier in individual posts. Terry can allow disallow them as he likes, but I did arrive at them after looking at this conversation.

21 July, 2009 at 7:15 am

David Escott

141a. Given a set where the Grasshopper can reach the end, you might be able to block the only possible path with a point in M. But the moment you add a another jump all bets are off, as that jump could be applied anywhere in the sequence. I’ll be very impressed if someone can make this work.

21 July, 2009 at 7:15 am

David Escott

141b. Speyer (2) mentioned a minimal size needed to disconnect. This seems a good approach. What is the minimal size needed to prevent the grasshopper from reaching its target. Clearly at least n will suffice as we could select M={a_1,…a_n}. What happens when we remove one element from M.

21 July, 2009 at 7:16 am

David Escott

141c. Final observation. The beginning an ending jumps are constrained. There are n possible first jumps, n possible last jumps, but n^2-n-O(A,2) which measures the number of instances where a_i+a_j=a_k+a_l. I’d avoid the middle and focus on the beginning/end of the sequence.

21 July, 2009 at 7:27 am

David Escott

141addendum. Apologies to Terry. I guess its just the WordPress spam filter.

21 July, 2009 at 7:33 am

David Escott

142. I wasn’t clear on 141c comment. There are n possible first landing positions. Then n^2-n-O(A,2) second landing positions, n^3-n^2+n-O(A,3) (I think…). Key point is the O(A,2) which measures the # of overlapping 2 sums in A. For A={1,2,3,4} O(A,2)=1 because 1+4=2+3 so there is one overlap. This function is clearly very complicated and changes every time you change A. If you are trying to analyze what happens in the middle of the path, I think it will cause serious problems for you.

21 July, 2009 at 7:37 am

Raghu

Here’s one way of making the following approach suggested by Gowers and others work.

Show by induction that for $k <= n$ you can take $k$ steps that avoid the mines $M$ .

The base cases have been discussed before. Suppose that you can take $k-1$ steps $a_1,a_2,...,a_{k-1}$ (in that order) without hitting a mine. Let $a_k < a_{k+1} < ... < a_n$ be the remaining possible steps and let $s = a_1+a_2 + ... + a_{k-1}$ . Now a strong observation is that if any of $s+a_k, s+ a_{k+1},...,s+a_n$ is not a mine we are done. And if not we 'know' the positions of $n-k+1$ mines.

In particular there are at most $k$ mines in the interval $[0,s+a_{k+1}]$ and at most $k-1$ mines in the right open interval $[0,s+a_{k+1})$ . Let $s' = s+ a_{k+1}$ . Then, from the above observations for some $1 <= i <= k+1$ , $s'-a_i$ is not a mine and the interval $[0,s'-a_i]$ has at most $k-1$ mines. We can now finish the argument by another level of induction on $k$.

21 July, 2009 at 7:41 am

jens

141. trying to fix proof 129.
Assume a_1<…<a_n, s=a_1+…+a_n, M the set to be avoided, m=max M.
The induction step works except if s-a_n=m:

Suppose s-a_nm, set M’=M\{m}, A’=A\{a_n}. By induction hypothesis
there is a permutation p in S_{n-1} s.t. for all j up to n-1 the sums
s_k=\sum_{i\leq k} a_{p(i)} are not in M’. If also s_k is not in
M for all k, we are done. Otherwise, there is k with s_k=m. Now we
replace the step a_{p(k)}=s_k-s_{k-1} by a_n which is larger than
a_{p(k)}. Done.

A similar argument “from the left” works if a_nmin M, however it
well may be the case that s-a_n=max M and a_n=min M.

21 July, 2009 at 7:48 am

Mark Bennet

143

I thought I had posted a potential set of equivalence relations between solutions [involving reduction and expansion operations]. A solution is everything stated in the problem, plus a specific path through the minefield (ie with designated jumping-off points). Different paths are different solutions.

In case Terry is filtering for too much info – can I suggest as a technique looking for an equivalence on solutions (someone suggested a stronger hypothesis, which put this in mind) – which allows reduction of solutions to simpler solutions.

Then the question is, can I build a solution for a particular configuration using the reverse of the equivalences? Here a possible technique is to find a good ordering on solutions which allows a minimal counterexample to be identified and proved not to exist.

21 July, 2009 at 7:52 am

Mark Bennet

Ref 143

I meant an ordering on configurations, not solutions.

21 July, 2009 at 8:00 am

Louigi

159. (Number based on total number of comments to date.) A small observation. Suppose that $a_1 < a_2 < \ldots < a_n$ and that the landmines are at $m_1 < m_2 < \ldots < m_{n-1}$ . Choose a sequence of steps that avoids as many land mines as possible, and suppose it lands on some mine $m_i$ . If the last step (the one that leads the walk to land on $m_i$ is $a_j$ then the walk must also have used $a_{j+1},\ldots,a_n$ . Otherwise, we could replace that last step by a large last step and avoid an additional mine ( $m_i$ ). I don't know exactly what to do with this. Maybe let $a_k$ be the largest unused step and replace one of the used steps with $a_k$ to avoid $m_i$ , or something?

21 July, 2009 at 8:06 am

emeritusl

144. Sorry if this is a repetition of an earlier comment. My previous comments did not make it and now I’m trying from a wordpress account.

Here’s one way of making the following approach suggested by Gowers and others work.

Show by induction that for $k <= n$ you can take $k$ steps that avoid the mines $M$ .

The base cases have been discussed before. Suppose that you can take $k-1$ steps $a_1,a_2,...,a_{k-1}$ (in that order) without hitting a mine. Let $a_k < a_{k+1} < ... < a_n$ be the remaining possible steps and let $latx s = a_1+a_2 + … + a_n$. Now a strong observation is that if any of $s+a_k, s+ a_{k+1},...,s+a_n$ is not a mine we are done. So suppose not. In this case we 'know' the positions of $n-k+1$ mines.

In particular there are at most $k$ mines in the interval $[0,s+a_{k+1}]$ and at most $k-1$ mines in the right open interval $[0,s+a_{k+1})$ . Let $s' = s+ a_{k+1}$ . Then, from the above observations for some $1 <= i <= k+1$ , $s'-a_i$ is not a mine and the interval $[0,s'-a_i]$ has at most k-1 mines. We can now finish the argument by another level of induction on k since k < n.

21 July, 2009 at 8:25 am

Mark Bennet

144

Given a solution (see 143) here are some equivalences.

The points the grasshopper hits are called jumping-off points, the distances between them are the Ai. Zero is a jumping off point. The mines are distributed some way along the number line from 1 to s-1. Spaces are points which are neither mines nor jumping off points. The gap between jumping-off points will be called an interval.

Equivalence 1 – spaces

Remove one or more spaces from any interval to reduce its length (provided I keep the Ai all different).
Add one or more spaces to any interval (eg the longest) provided its final length is not one of the Ai.

These keep n the same and alter one of the Ai (hence also s).

21 July, 2009 at 8:28 am

Mark Bennet

146

Equivalence 2 – intervals with single mines

Remove any interval with a single mine, merging its two endpoints into one.

Take any jumping off point, and replace it by an interval containing a single mine, provided is length is not one of the existing Ai.

These change n by 1, and introduce or remove a single interval.

21 July, 2009 at 8:38 am

Mark Bennet

147

Equivalence 3 – intervals with more than one mine

Using no 2, I can make sure no interval contains a single mine if I want to. So all my intervals are empty or contain more than one mine. A simple counting argument says I must have at least one empty interval.

If I have an interval with more than one mine in it, and an interval containing r spaces, I can remove the empty interval (collapsing the two endpoints to one) and replace one of the mines with a space.

If I have an interval with a space in it, I can replace the space with a mine and replace any jumping off point with an interval of length r, provided r is not one of the existing Ai.

These reduce or increase n by 1, with a corresponding reduction or increase in the number of empty intervals.

21 July, 2009 at 8:47 am

Mark Bennet

148

The equivalences come in pairs for reducing and expanding

21 July, 2009 at 8:51 am

pablolessa

149.

To David Speyer 139.

An example of the case you propose is the following:

$A = \{1,\ldots, n\}$
$M = \{b+1,\ldots, b+n-1\}$

If we remove $n$ from $A$ and $b+n-1$ from $M$ , any path we obtain by induction will land exactly on $b+n-1$ .

For the case $A = \{1,\ldots,n\}$ it seems to me that the fact that there is a residue class modulo $n$ without landmines is very helpfull (and handles the above situation nicely).

This residue class splits ${}0,\ldots, n(n+1)/2$ into a number of intervals. Is it true we should allways use $n$ to jump over the interval with the most landmines?

21 July, 2009 at 9:10 am

Mark Bennet

150

In response to 149

If there are three landmines at positions 1,2, and 4, and the Ai are {1,2,3,4} you need to use the 3 to jump the first two mines – and you can’t use the 4.

21 July, 2009 at 9:14 am

Tony

I wonder whether the marriage theorem can be used. Let A(x) be a collection of subsets r of A such that the sum of the elements of r < x. Suppose that the elements of M are ordered m1 < m2 <…< m_(n-1) < s. Then we have A(m1) in A(m2) in A(m3) in … in A(m_(n-1)) in A(s). Can we select a set rk from A(mk) such that r1 in r2 in … in r_(n-1) in rn? Note A(s) contains only A.

21 July, 2009 at 9:14 am

David Speyer

151 To Pablolessa: what is b?

21 July, 2009 at 9:22 am

IMO 2009 Q6 mini-polymath project cont. « What’s new

[…] July, 2009 in math.CO | Tags: mini-polymath1 | by Terence Tao Well, participation in the IMO 2009 Q6 polymath project has exceeded my expectations; it appears that the collaborative effort has scored some partial […]

21 July, 2009 at 9:25 am

Terence Tao

Note: as this thread is becoming quite full, I am closing it and moving on to a fresh thread:

IMO 2009 Q6 mini-polymath project cont.

This may cause some temporary discontinuity in the discussions, but I think this will be better in the long run, as it should assist in letting readers catch up with things. I recommend that participants use this transition to try to summarise the state of the project so far.

21 July, 2009 at 11:31 am

Pedro Vieira consegue um feito histórico: a primeira medalha de prata portuguesa nas Olimpíadas Internacionais de Matemática « problemas | teoremas

[…] o tentassem resolver de forma colaborativa, havendo já mais de centena e meia de comentários, no post respectivo, pelo que decidiu abrir um segundo […]

21 July, 2009 at 4:13 pm

Top Posts « WordPress.com

[…] IMO 2009 Q6 as a mini-polymath project The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four […] […]

27 July, 2009 at 10:24 am

Reading for today « Shores of the Dirac Sea

[…] smart, how about you try solving problem number 6 of the IMO without peeking. I found about it here, but I have not had time to even attempt to solve it. It sounds like […]

1 August, 2009 at 5:37 pm

Mini Polymath « OU Math Club

[…] In the meanwhile, Terence Tao is running a mini-polymath project. The problem is the sixth (and hardest) problem from the 2009 International Math Olympiad. The problem is: […]

2 August, 2009 at 9:28 am

A mini-polymath project « Euclidean Ramsey Theory

[…] https://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ […]

21 February, 2010 at 8:44 am

Bài toán số 6 trong IMO 2009 « Sharing

[…] link 2 […]

17 March, 2010 at 11:34 am

Polymath Reflections « Combinatorics and more

[…] Polymath4 devoted to deterministically finding primes that took place on a special polymathblog, a miniPolymath leading to collectively solving an olympiad problem, and an intensive Polymath5 devoted to the […]

12 June, 2010 at 3:09 pm

Future mini-polymath project: 2010 IMO Q6? « What’s new

[…] rules. The rules for the first mini-polymath project can be found here. Basically the spirit of the rules is that the objective is not to be the first to produce an […]

9 April, 2012 at 9:06 am

inamerrata » Blog Archive » Solving hard Maths Olympiad problems

[…] it’s IMO season, and in honour of such, Terry Tao reposed one of the questions on his blog as a “polymath” project — something to be solved collaboratively over […]

12 July, 2012 at 10:31 am

Polymath project: social problem-solving | Civil Statistician

[…] around the world use a blog and wiki to work together on one of that year’s IMO problems. His 2009 post is a good introduction to the event and the spirit behind it. Personally, I had a blast trying to […]

3 May, 2015 at 4:49 pm

Counting what’s important | Oliver Nash's Blog

[…] Q6 (expected score 0.17) [Thanks to Terry Tao this problem attracted some attention at the […]

	Aleksandar on 245C, Notes 4: Sobolev sp…
	Anonymous on Erratum for “An inverse…
	Anonymous on Erratum for “An inverse…
	Anonymous on Erratum for “An inverse…
	Anonymous on Erratum for “An inverse…
	Terence Tao on 245C, Notes 4: Sobolev sp…
	Terence Tao on 275A, Notes 3: The weak and st…
	Terence Tao on What is a gauge?
	Terence Tao on Erratum for “An inverse…
	Terence Tao on 275A, Notes 3: The weak and st…
	Terence Tao on An epsilon of room: pages from…
	Aleksandar on 245C, Notes 4: Sobolev sp…
	Anonymous on Some notes on amenability
	Anonymous on On writing
	Anonymous on 275A, Notes 3: The weak and st…

IMO 2009 Q6 as a mini-polymath project

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

184 comments

For commenters

IMO 2009 Q6 as a mini-polymath project

Share this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

184 comments

For commenters