Well, participation in the IMO 2009 Q6 polymath project has exceeded my expectations; it appears that the collaborative effort has scored some partial successes toward a solution in the first 24 hours of its existence, but is not quite there yet.

As the thread has become overly long, I am following established polymath practice and starting a new thread here, hopefully to try to impose more order onto the chaos. In order to assist this effort, some of the participants may wish to summarise some of the “state of play” so far. (I am unable to do this due to being biased by the knowledge of a solution.)

The comment numbering system has not worked as smoothly as I had hoped, but it is still better than nothing. I propose that comments in this thread start at 200, so as not to collide with the previous thread.

Of course, all the rules of the polymath exercise (as discussed in the previous thread) continue to apply. I am pleased to see that virtually everyone participating has adhered to the collaborative spirit of the exercise, for instance in keeping criticism constructive and technical rather than pejorative and personal.

As an experiment, I have enabled one level of comment threading; thus one can reply to a specific comment in the thread below. If one does so, I would request that you number the comment by subsection, for instance the first response to comment 234 would be numbered 234.1, the next one 234.2, and so forth. There is a tradeoff here; the threading adds more structure to the comments, but the flip side of this is that it makes it harder to read off at a glance all the comments made since the last time one checks the thread. Hopefully participants will be able to use their discretion when to reply and when not to. [*Update*, Jul 21: Threading should work properly now, I didn’t set it properly before.]

### Like this:

Like Loading...

*Related*

## 172 comments

Comments feed for this article

21 July, 2009 at 9:34 am

SW201. A few comments (2, 141b etc) have suggested taking a topological approach, viewing partial sums of the as subsets of and thus as vertices on the n-cube. Each vertex/subset gets mapped to the integers by the sum function, and one can therefore take a quotient of the graph by identifying vertices with the same sum. The problem then would seem to deal with the number of vertices one might remove in order to disconnect the empty set vertex with the opposite corner.

My comment is that the grasshopper cannot move backward, whereas one might do so on the n-cube. Thus showing that removing n-1 vertices from the quotient cannot disconnect is not sufficient. You could change it to a directed graph, but then Menger’s theorem on graph connectivity does not seem to apply and the topology becomes more complicated.

21 July, 2009 at 9:45 am

SW202. Another line of thought has focused on figuring out how to place (or some other big jump) so that it can jump the maximum number of mines.

If we can use the first or last jump to jump a mine we are done by induction, so we may as well assume that we cannot (in particular, both and are henceforth assumed to be in ). That means we have jumps in the middle to hop over mines; at least one jump must go over 2 mines. A few comments have asked if we can prove that there must be two mines close enough to be jumped simultaneously (answer: yes) and also whether it must be the case that we can choose to be one of the jumps that does so (answer: no; see comment 150, but note that this example is one in which the easy induction argument applies, so perhaps if we avoid these cases…?).

21 July, 2009 at 9:50 am

Anonymous201. Status

It appears that there are two (related) proposed solutions standing at this time.

(1) The first is contained in posts 125 and 129, with follow up threads at 130, 131, 132, 136, 137, 138, 141, 149, 151.

(2) The second is contained in the posts “Raghu 7:37 am” and 141 (8:06 am).

Can I suggest that we take a look at these and either turn them into clean proofs or identify any issues? Of course, this should not discourage other approaches/discusion.

21 July, 2009 at 9:53 am

Raghu202. I posted an argument in comment 144 (http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/#comment-40403) but there is a mistake in it. There’s perhaps something to salvage. Here’s a summary of the approach suggested by Gowers and others.

Approach: Show that for 0 < k < n we can take k steps without hitting a mine.

For induction suppose we can take k-1 steps and . The point now is that if we can't take one more step then must all be mines so that many mines are within one 'interval'. Perhaps there's a way of exploiting it ….

21 July, 2009 at 10:12 am

Mark Bennet204 – ref 202

An and s-An could be empty, rather than in M, and it would still prevent the induction going through. This bunches things up in the middle, though.

21 July, 2009 at 10:14 am

Louigi205. A small observation, not terribly linked to either of the approaches described above. Suppose that and that the landmines are at . Choose a sequence of steps that avoids as many land mines as possible, and suppose it lands on some mine . If the last step (the one that leads the walk to land on is then the walk must also have used . Otherwise, we could replace that last step by a large last step and avoid an additional mine (). I don't know exactly what to do with this. Maybe let be the largest unused step and replace one of the used steps with to avoid ?

21 July, 2009 at 10:20 am

Kristal CantwellIf you are looking at the problem for n and your are looking at the sums of n-1 elements then the sum of the largest n-1 elements cannot be in M. If it is any of the other sums of n-1 elements is missing from M then it will take n elements to block the set of n-1 elements making up the sum by induction so all such numbers must be in M but that gives a total of n elements and M has n-1. So the sum of the largest n-1 elements is not in M and further by induction that means that it will take n elements to block the set of the n-1 elements making up the sum by induction so what we have is that every element of M is the sum of n-2 or less elements of the set of the n-1 largest elements of the n set a_n. I am not sure useful this is though.

21 July, 2009 at 10:28 am

pablolessa206. Another attempt at a summary, I’ll go ahead and say that I’m biased to try to find a solution for :

———

One of the main obstacles in this problem is that diferent subsets of the set may have the same sum, and therefore a single landmine may block several paths.

In accordance with this, the case (in which all subsets have different sums) has been solved by a simple counting argument (see 27).

Also, numerical experiments have shown that, in general, landmines can block a substantial number of paths and this has casted a lot of doubt on the possible success of counting arguments (e.g. 71,72,73).

All this experience seems to indicate that the worst possible case is .

— Progress for —

This case has been solved in self contained manner for but the arguments don’t seem to generalize (18,60).

For larger it was pointed out that there exists a residue class modulo without landmines. Also an argument was given for but it’s not self contained and seems to rely on the inductive argument explained below (124).

None of the arguments given seem to generalize easily for larger although they haven’t been explored in depth.

The special case in which there are consecutive landmines has been singled out a couple of times (e.g. 51). It shows that one cannot choose the first (or last) step arbitrarily among the available options, and therefore proposed solutions that do so, must be examined carefully.

— Induction —

Let’s return to general .

In the attempt to find a way to use induction, the following lemma was identified several times (e.g. 112):

“If we can jump over or more landmines with jumps then induction can be used to complete the solution”

Also there is an obvious “forward-backward” symmetry that can be exploited in certain cases.

— Reformulations —

A number of abstract formulations of the problem have appeared. The most discussed deals with the cube or quotients of it. Out of this a subdiscussion involving Mengers theorem grew, but I am not qualified to comment on it (see 201).

— Proposed proofs —

There are a couple of proposed proofs:

One of the comments numbered 140. (the one by liuxiaochuan) seems to me to give a clear argument that we can jump at least twice, but I couldn’t quite get the following inductive step.

Another proposed proof starts off by removing from and the largest landmine from . The number is choosen so that .

The next step in this proposed proof is to use induction to find a path avoiding and ending at .

The final step in the argument is to modify this path (half of it actually) in order to avoid the remaining landmine.

The implicit concensus seems to be that the proposed proofs aren’t quite correct yet, but might be fixable. Both of them (but especially the first one) seem to run in to the problem of choosing the first or last step arbitrarily based on local infomatin (see above, and also 51.).

21 July, 2009 at 10:30 am

liu xiaochuan206 I just can’t leave any comment.

21 July, 2009 at 10:32 am

liu xiaochuan207 I have tried at least twenty times to leave a comment and still can’t see them, though it always tell me that I duplicated the same comment.I guess the same situation happens to David,too. Maybe it is because our comments are too lengthy,since the last one is ok.

21 July, 2009 at 10:33 am

Anonymous207. Logistical Question: How does the (one level of) comment threading work?

21 July, 2009 at 10:39 am

liu xiaochuanLet .

1,can't be blocked, otherwise we can choose our first step to left a landmine behind, finish the inductive step.

2, Two sets and contains at least n different values. we claim that the elements in B should not be all blocked. otherwise we can choose the first step with and then leaving all landmines behind.

3,so, we can at least get to the second group withour being killed. then we claim that and can't be all blocked. otherwise we can take two steps and leave two landmines behind and finish the inductive step.

4, through or , we can get to

,

which contains at least n-1 different values. Similarly, if all of these are blocked, then we can construct a way to avoid all of the landmines. So, we can get to one of these by the third step.

5, then we analyze in the similar fasion and continue in the road.

21 July, 2009 at 10:42 am

Kristal Cantwell208.

I think there is a length based filter. I have problems with longer posts being held up. I now try to break them up. I am not sure what length triggers the filter.

21 July, 2009 at 10:45 am

Mark Bennet208

Can I put in a word for creating an equivalence relation between solutions, which allows any solution to be reduced to something trivial. [A solution is a configuration Ai, n, s, M; together with a specific path through the minefield] (see 143, 144-148) and some machinery to order configurations so we can prove the non-existence of a minimal counterexample.

21 July, 2009 at 10:47 am

CristinaI was not able to leave a comment, either — curious if this is going through.

21 July, 2009 at 10:52 am

Mark Bennet209

In fact, does ordering solutions to find a minimal counterexample help anyway.

Look at this possibility:

First we choose the minimum value of n for a counterexample.

Amongst such values of n we choose the Ai and M so that we can choose a permutation of the Ai which minimises the number of hits on mines over all counterexamples for such n.

Then “all” we need to achieve is a rearrangement which avoids one hit, and we’re done.

Or maybe minimising n is irrelevant, and a counterexample with the minimum number of hits is the thing. Then there might be some flexibility to jiggle the proposed counterexample in a reversible manner to prove that it was not minimal.

21 July, 2009 at 10:53 am

Cristina209.Bit of a tangential idea to some posts (eg.Raghu, Gowers) based on the fact that the elements in A are distinct-maybe can be used to fix some things.

If no permutations exist, then k<n exists for which all arrangements of k elements from A lead to an impasse: a1+a2+…+ak=mi, where mi is one of the elements in M (we'll have n!/(n-k)! such sums/equalities)

Maybe these partial sums being simultaneously equal to elements from M leads to an equality of the form ai=aj, which is contrary to the original hypothesis?

21 July, 2009 at 10:55 am

partalopoulo210. It looks like the server was holding back some posts (because of length?). I apologize for the repetition, but there were constantly problems with my posts (missing text, latex code not appearing etc.).

I will attempt to post the suggestive the suggested proof as a whole again. I’ll avoid using latex so that there will be no missing text. I also rewrote the last part of it to make it clearer.

This will be done in 2-3 posts.

21 July, 2009 at 10:55 am

partalopouloInduct on n. For n=2 see post 4@Lugo and for n=3 see post 18@gowers. Assume it holds for 2,3,…,n-1. Let M and A={a_1,…,a_n} be as in the statement. Set m=max(M). WLOG assume that m<s. We have that at least one of the numbers S-a_i is NOT contained in M, since card(M)<n. WLOG assume that S-a_n is the one not contained in M.

Set M'=M-{m} and A'=A-{a_n}. Apply the induction hypothesis on A' and M'. So there exists some permutation t in S_{n-1} so that the numbers S_j:=a_{t(1)}+…+a_{t(j)} do not belong to M'.

If S_{n-1}=a_1+\cdots a_{n-1}<max(M'), we are done (choose a_n as the last step), so assume this is not the case. Also, if max(M')1).

21 July, 2009 at 10:56 am

David EscottMark (208),

Isn’t your equivalence relation going to reduce all paths to one big jump. Doesn’t it just say that all successful solutions are equivalent in that they are successful. Did I miss something?

21 July, 2009 at 11:04 am

AnonymousLet me try to address proposed solution (2) listed in the summary post 201. The original posts are “Raghu 7:37 am” and 141 (8:06 am).

The author writes: Suppose that you can take steps (in that order) without hitting a mine. Let be the remaining possible steps and let . Now a strong observation is that if any of the is not a mine we are done.

I think this last assertion is false. In order to perform the induction we need to remove an element from (this element is above) AND a mine. The problem (which has come up before) is that when we include this mine back in it may destroy the path of elements we obtain from the previous case of the induction.

21 July, 2009 at 11:09 am

PhilG213. “half-dozen or so managed to solve this problem completely”

There could be a non-obvious observation that resolves this quickly.

21 July, 2009 at 11:09 am

CristinaWhat if the fact that all the possible partial sums at a step k (for any initial a1) take to a mine leads to an equality between two of elements in A, which is contrary to the hypothesis?

21 July, 2009 at 11:13 am

Anonymous215 partalopoulo 210– Thanks for offering to repose your idea. I was having some trouble following it towards the end (particularly, I assume the 12 was a typo?) — maybe you could reword the last paragraph?

21 July, 2009 at 11:14 am

David Escott216 I believe there should be a correspondence of minimal blocking sets constructed as follows:

Let M={m_1<m_2…<m_n} be minimal blocking set. Let F=sum(a_i). Then if we remove m_k from M we allow at least one path. Furthermore all these paths must pass through m_k, just as all paths must pass through start=0 and finish=F. Therefore, I think we can shuffle these minimal blocking sets

Construct M'={F-m_i|ik} union {F-m_k}. I believe it should still block.

Can this symmetry perhaps be used to get the minimal blocking set into a nice form.

21 July, 2009 at 11:16 am

brummSPOILER Complete proof

Induction: Case n is already proved -> Case n+1

(Induction start is trivial)

We make no further assumptions about M and a_i (i.e. we do NOT generate M_n+1 from M_n as some faulty proofs do).

Let’s call the largest of the a_i “max a” (there’s a single max a since they are all distinct). Let’s call the sum of the a_i “target”.

Let f be the number of mines in the interval (0,max a).

Now we have the following cases:

* max a is a mine and f>0. In that case, out of the a_i that are not max a (n numbers), at least n-f are not mined (when taken as a first jump). Consider the n double jumps (a_i != max a, max a). At least n-f of those are not mined on first jump. The number of mines in (max a, target) is the number of mines (n) less f less the one for max a, yielding n-f-1 which is less than n-f. Thus by counting argument, at least one of the double jumps does not hit a mine on both jumps. This double jump takes two jumps and jumps over f+1 >=2 mines, yielding a problem with n-2 mines and n-1 remaining jumps, which is solved by induction.

* max a is not a mine and f>0. Take max a as first jump, yielding problem with n remaining jumps and n-f<n mines, which is solved by induction.

* max a is a mine and f=0. Let min M be the smallest mine in M. Construct M'=M\{min M}. Jump max a as the first jump and solve the n-problem with the remaining a_i and M' by recursion, I mean induction. Let a_x be the first jump of this solution. Exchange max a and a_x (i.e. jump a_x first then max a). max a+a_x is no mine (guaranteed by solution), a_x is no mine (because a_x < max a == min M as above). There are no mines in the rest. We have completed solution for n+1.

* max a is not a mine and f=0. As in case 3, construct M', jump max a first and solve for the remaining a_i and M'. If this solution hits min M in step k, construct a new solution by exchanging step k+1 and step 1 (i.e. max a). There are no mines before min M, thus the mine is avoided and no new mines are hit. We have completed solution for n+1

I hope that's it and it's shut tight. This problem is just evil

.

21 July, 2009 at 3:47 pm

David EscottWell done… did any part of the thread help you?

22 July, 2009 at 3:30 am

BenoitIt seems right to me, but may be to complicated formulated this way.

First, if there is a mine at all in (0,max a) then the induction works as has been noticed. Otherwise, use the induction to solve the problem of going from max a to s using the n-1 smallest a_i and avoiding the n-2 largest mines. If, when adding the first mine it blows up the grasshopper, then you can switch the a_i that was used to from this first mine with max a to avoid it. You won’t encounter any other mine this way because there is none before the one you just add.

21 July, 2009 at 11:16 am

David Escott216 This spam filter is annoying. If you have a minimal blocking set, I think you can pivot it around any point in the minimal set, by removing that point, swapping the front and back, and adding the point corresponding to the original endpoint. Might this be used to normalize the form of the minimal blocking sets, and thus prove their size is at least n.

21 July, 2009 at 11:17 am

AnonymousLogistics: Having trouble posting comments. Checking if problem is the length of comment.

21 July, 2009 at 11:22 am

Raghu217. @Anonymous 21 July, 2009 at 11:04 am – You are right in that there’s a mistake in the argument, but it is not the one you mention: the induction is over k (n is fixed). The observation that should all be mines could still be useful though.

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[…] Adenda de 21.07.09: outro problema, do mesmo dia, considerado particularmente difícil por Terence Tao é o n.º 6. Sobre ele o Professor propôs, ontem, no seu blogue, que os seus leitores 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 post. […]

21 July, 2009 at 11:35 am

partalopoulo218. To Anonymous at 215. I have a very hard time posting my comments. I will try again.

Continuing post 210:

We perform induction on n. For n=2 it is true. Assume it is true for 2,…,n-1. Let A={a_1,…,a_n} and M as in the statement. For one of the a_i we have that s-a_i is not in M because card(M)<n. WLOG assume this is a_n. Set m=max(M), M'=M-{m}, A'=A-{a_n} and m'=max(M').

To be continued….

21 July, 2009 at 11:37 am

partalopoulo218. To Anonymous at 215. It’s impossible for me to post anything. The server is not accepting it. I’ll try again later.

21 July, 2009 at 12:14 pm

K219. I just saw this post. I think they way to go is extend the idea in n=2 and use induction. Since there are n-1 numbers in the set, at least one of s-a_i s is not in it. Use a_i as the last jump.

21 July, 2009 at 12:16 pm

K219. I just saw this post. I think the way to go is extend the idea in n=2 and use induction. Since there are n-1 numbers in the set, at least one of s-a_i s is not in it. Use a_i as the last jump.

21 July, 2009 at 12:24 pm

K220. Adding to 219: To reduce the set, there should be at least one possible a_i such that one of the members of the set is above s-a_i.

21 July, 2009 at 12:27 pm

a.s.In the case of A={1…n}, the “worst” cases seem to be blocks of landmines M={2,3,…,n} or M={3,4,…,n+1}, and two “symmetric” sets ending at N-3 and N-2 (with N=n(n+1)/2). Obviously, in this four cases we are left with (n-2)! paths, other sets M leaving many more possibilities. Tested experimentally for n=2..7; can it be of any help for counting or an induction hypothesis?

21 July, 2009 at 12:29 pm

pablolessa222. I’d like to discuss an idea for a very special case, which I think might be of some general value.

Take and suppose that there are no mines in the set .

This set divides into four equal intervals of length . The idea is to jump over each of them by using either , or one of the pairs .

In order to simplify the discussion I will include a jump of length zero, so that we have four pairs of jumps available (note that most pairs can be used in two different ways).

——-

The following observations are the key to the argument:

*Any given pair of jumps will be able to pass over an interval with zero or one mines, without hitting a landmine.

*Given two pairs of jumps, it is garanteed one of them will be able to pass an interval with two or three mines.

*Given any three pairs, one of them will be able to jump over an interval with four or five mines.

——-

Order the four intervals by decreasing number of landmines.

The first interval has at most mines.

The second interval has at most mines.

The third interval has at most mines.

The fourth interval has at most mine.

Therefore we can pass the first one with a pair. Pass the second one with one of the remaining three pairs. Pass the third one with one of the remaining two pairs. And the last one is garanteed to be passed safely by the only remaining pair of jumps.

I think this argument might generalize to with odd , when there are no landmines on multiples of .

But I also think that if is arbitrary and another residue class modulo has no landmines, we might be able to adapt the argument to deal with the two smaller intervals at and .

21 July, 2009 at 1:04 pm

Anonymous223. brumm 11:16am.

I haven’t fully digested your argument, but I have a question on the following line.

You write:

max a is a mine and f=0. Let min M be the smallest mine in M. Construct M’=M\{min M}. Jump max a as the first jump and solve the n-problem with the remaining a_i and M’ by recursion, I mean induction.

Since max a is a mine (by assumption) aren’t we going to run into trouble if we take max a as the first jump?

21 July, 2009 at 1:06 pm

Anonymous224. @223 No that mine has been temporarily from M to construct M’.

21 July, 2009 at 1:07 pm

AnonymousOh I accidentally the whole mine.

21 July, 2009 at 1:08 pm

Anonymous225 @ 224. But isn’t is the min M that we remove to construct M, not max M.

21 July, 2009 at 1:08 pm

gbaloglou224. Let Nk be the number of obstacles at the k-node level, k = 1, …, n-1. Each obstacle at that level kills (n-k)! paths from A1+…+An to 0 *and* it appears k! times at that level. There is a total of n! such paths, while SUM[Nk] = n-1. It looks at first that this does it because of SUM[Nk] = n-1 —-> SUM[Nk(n-k)!k!] < n! … BUT the same obstacle may appear at two distinct levels!

Let me illustrate this by reference to my example (that I linked here yesterday). Given obstacles {3, 8, 20} we get N1 = N2 = N3 = 1; we also see that 3 appears 3! times at level-3, 8 appears 2! times at level-2, and 20 appears 1! times at level-1. The formula SUM[Nk(n-k)!k!] yields 1*3!*1! + 1*2!*2! + 1*1!*3! = 6 + 4 + 6 = 14 24 … but there is double counting, too!)

21 July, 2009 at 1:11 pm

gbaloglou227. My comment (224, should be 226) has been truncated — I forgot that business about inequality signs :-(

21 July, 2009 at 1:12 pm

Henry228. Here’s a way of proving that there is a path of length 3 which has a more inductive character. As in 107, choose b_1,b_2 from among the a_i such that b_1+b_2 is the largest possible value after a path of length 2, and b_1 is the largest first value which begins a path of length 2 with this sum. Suppose there is no path of length 3 extending this path; that is, b_1+b_2+a_i is in M whenever a_i is neither b_1 nor b_2. Note that this accounts for all but one element of M.

Let c_1,c_2 be the smallest a_i other than b_1 and b_2. Suppose we could show that c_1<b_1 and c_1+b_2+c_2 not in M; then there would be at most two smaller elements of M smaller, and so by induction, a path of length 3 leading to c_1+b_2+c_2. Similarly if we could show c_1<b_2 and b_1+c_1+c_2 not in M.

First, observe that at most one of b_1+c_1 and b_2+c_2 belong to M, and by the maximality of b_1+b_2, it follows that either c_1<b_1 or c_1<b_2. Suppose it is not the case that c_1<b_2; then b_2+c_1 is in M and c_1<b_1, so in particular b_2+c_1<c_1+b_2+c_2<b_1+b_2+c_2 and c_1+b_2+c_2 is not b_1+b_2+c_2, and therefore c_1+b_2+c_2 is not in M.

Similarly, if it is not the case that c_1<b_1 then b_1+c_1 is in M and c_1<b_2, so it follows that b_1+c_1<b_1+c_1+c_2<b_1+b_2+c_2 and b_1+c_1+c_2!=b_1+b_2+c_1, so b_1+c_1+c_2 is not in M.

If both c_1<b_1 and c_1<b_2, it follows that both b_1+c_1+c_2 and c_1+b_2+c_2 are less than b_1+b_2+c_2 and distinct from b_1+b_2+c_1; therefore at most one is in M, and we are done.

21 July, 2009 at 1:14 pm

Kyle Hofmann223. It seems to me that most of the comments so far have focused on trying to pass a group of land mines with a single jump. A problem with this “one jump at a time” approach is that you may need to set yourself up for that jump.

For example, consider the set . Here . Take . Suppose that we choose our first jump to be of length five. Then for a jump of length , where is any number between one and four, we get blown up. But we can do nothing else, because we have already used our jump of length five.

Instead, we must make two jumps before jumping any mines at all: We may make the jumps 1 + 4, 4 + 1, 2 + 3, or 3 + 2, and then we must make the jump of length five. The numerics on this strategy look bad, actually: We use up two jumps and pass zero mines, so we are left with three jumps to cross four mines! Somehow it works anyway because the same bad distribution that forces us to make two jumps at the start also forces us to jump four mines at once.

If we’re going to use some sort of induction (which feels like the way to go to me), then my best guess is that we should set it up like this: Assume that the statement is true if A has less than n elements; now prove that there is always a way to reduce to the same statement with less than n elements (not necessarily n-1 elements, which won’t work as above). This is of course hard, but the other inductive strategy we seem to have is to include some information about the distribution of the elements of M; and that strikes me as harder.

21 July, 2009 at 1:16 pm

ar230. @sw (201). Regarding the graph approach, it’s true that Menger’s theorem does not seem to apply because you need to take the graph directed. But in fact we don’t need Menger’s theorem at all. If there are n vertex independent paths between the “0 vertex” and the “total sum vertex”, obviously there is no way to disconnect them taking out n-1 vertices (each vertex you take out will belong to at most one path).

What Menger’s theorem would say (if applicable) is that the “n disconnecting vertices” statement and the “n vertex independent paths” statement are equivalent. Without Menger’s theorem, the “n vertex independent paths” statement could happen to be wrong… Anyway, this still seems worth thinking to me.

21 July, 2009 at 1:17 pm

Mark Bennet223

David – my equivalence relation can reduce every solution to the trivial case where n=1,s=1,A1=1 and there are no mines.

The point is that every step is reversible, so:

(a) can a sequence of ‘going up’ steps be used to construct a solution by brute force? [difficult, but there is a richer set of options, it seems to me, than simply permutations of the Ai]

(b) by studying the space of solutions through equivalence, can we prove that every configuration is solvable: eg by proving that a hypothetical minimal counterexample can’t exist? [again the richer set of options might help here]

I think it is possible to put quite severe conditions on a hypothetical minimal counterexample by defining the order well. Then it is necessary to have sufficient flexibility to show that a smaller counterexample must exist. [I’m reminded of Kempe chains to prove the five colour theorem]

It seems indicated to me that such factors as the Ai being distinct are crucial to the proof, because there are counterexamples otherwise. So any proof which does not, in some way, use this fact, cannot succeed.

The problem has various local obstructions to a route through, which may require global solutions – in that a route which seems “to nearly work” may be quite distant (in some intuitive sense) from any actual solution.

21 July, 2009 at 1:22 pm

ar232. Let me write the graph restatment again. Construct an n-cube putting a subset of {1,…n} at each vertex and a directed edge from A to for any and . Every vertex is labelled by the integer , and every edge by the corresponding to the index that the edge adds to the set at the source.

Now take the quotient of this graph G identifying vertices with the same label and edges with the same edge label and vertex label at both, source and target. If we prove that there are at least n vertex-independent paths (i.e. without vertices in common except from the endpoints) joining the empty set to {1,…n} in the graph G we are done !

An other way to say the same is as follows: Find n vertex-independent paths from the empty set to {1,…n} in the n-cube but now the paths may be discontinuous, allowing a teletransportation from one vertex to another with the same label (ah, and the independence condition also knows about teletransportation … otherwise it would be easy).

By the way, the graph G is a piece of the Cayley Graph of the group of the integers with respect to the set of generators {a_1/d,…,a_n/d} and d = gcd(a_1,…a_n).

21 July, 2009 at 2:08 pm

David Speyer233 ar: If I understand you correctly, what you want is impossible. Take A = (1,2,3). Then there are not three independent paths from 0 to 6. Proof: The paths are p=(0,1,4,6), q=(0,2,5,6) and four others, each of which contain 3. So precisely one of the paths containing 3 must be used. But each of these is either incompatible with p or with q.

21 July, 2009 at 2:14 pm

jens233. Just a general thought on “almost complete” proofs by induction (as 129. and follow-ups), i.e. where the reduction of the problem to smaller problems works except in seemingly rather special cases:

I think that those proofs might still be far from completion, because I have the feeling that the “input data” for the induction hypothesis might typically be of that very special form. (It slightly reminds me of complexity theory…)

21 July, 2009 at 2:19 pm

Anonymous234. SPOILER warning inherited from brumm’s comment.

Re 225: You’re wondering about the case where max A is a mine and f = 0. I will try to rephrase brumm’s comment in this case more precisely but perhaps less clearly.

In this case max A = min M. Get A’ and M’ for induction by subtracting max A (=min M) from each element of A and M, then removing the resulting 0 element from each set. Use induction to get a path through A’ avoiding mines in M’. Call P’ the permutation of elements of A’ that define this path. Let x be min A. Then you can get P as (P'(1), x, P'(2)+x, … P'(N)+x). This cleverness avoids the pesky first mine, while allowing induction to avoid the rest of them.

21 July, 2009 at 2:32 pm

d234. I’m a bit late to the party, but what about this idea:

(*) if there are ever k (some 1 <= k = 1 element of M that is greater than s – max(a_j) so reversing (making that the “last” jump”) we would still be done by induction (apply (*) where we have reversed M and the a_j).

maybe i’m missing something, i’ve only just thought about this.

21 July, 2009 at 2:34 pm

d234.1 (Your blog munged my comment so I’ll try again)

234. I’m a bit late to the party, but what about this idea:

(*) if there are ever k (some 1 <= k = 1 element of M that is greater than s – max(a_j) so reversing (making that the “last” jump”) we would still be done by induction (apply (*) where we have reversed M and the a_j).

maybe i’m missing something, i’ve only just thought about this.

21 July, 2009 at 2:32 pm

David EscottMark (223)… You start assuming there is a solution, and then use your relation to show that the solution is in the class of solutions. How would you use your equivalence relations to show there is not a solution to the problem when M=A.

21 July, 2009 at 3:02 pm

Mark BennetDavid

I’m not assuming what you suggest. In the spirit of polymath, I’m proposing a path to solution different from that suggested so far.

I’m not quite sure of the definition of A.

I think that my most useful point is that a hypothetical minimal counterexample (eg to induction) can be more tightly drawn than most ofthe suggestions proposed elsewhere.

I can choose the lowest possible n. I can choose the first mine as close to zero as possible given n. Or I can choose the largest mine to have the smallest index possible. Or I can choose the set M to have the lowest possible index sum (all attempts to get the mines as far left as possible so that initial jums have a better chance of k jumps covering k mines and induction following).

Or I can choose the hypothetical counterexample which has the minimum number of landings on mines.

In each case I want to show that this is not a counterexample, or it is not minimal.

Then my question is “what tools do I have to do this?” The standard set is the permutations of the Ai. Are there other options?

Equivalence is a possible set of options – are they useful, do they work, are they necessary? I haven’t sat down to check.

21 July, 2009 at 2:32 pm

Anonymous235. SPOILER

Sorry I botched that a bit. I’ll try again.

In this case max A = min M. Get A’ by removing max A. Get M’ for induction by subtracting min M from each element of M and removing the resulting 0. Use induction to get a path through A’ avoiding mines in M’. Call P’ the permutation of elements of A’ that defines this path. Then you can get P as (P’(1), min A, P’(2), … P’(N)). P is the path through A that avoids mines in M.

21 July, 2009 at 4:04 pm

carmen237. Lets consider again the sets

A0={0}

A1={a1, a2, …, an} (the initial set)

A2={a1+a2, a1+a3, a1+a4, …, a1+an, a2+a3, ..,a2+an, …, an-1+an}

A3={a1+a2+a3, a1+a2+a4, …}

…

An={a1+a2+…+an}

We know that |Ak|=|A_{n-k}|, k=0,1,…,n

Using induction, we will be done if any element from A1 or A_{n-1} would belong to M. So we may suppose that this two set do not intersect M.

We also know that

|A1|=|An-1|=n

|A2|=|An-2|>=n-1+n-2=2n-3>n, n>1

|A3|=|An-3|>=n-2+n-3+n-4=3n-7>n, n>1

21 July, 2009 at 3:49 pm

pablolessa236. I’ve worked through brumm’s proof. It seems to me that it works fine.

21 July, 2009 at 4:09 pm

David Speyer237 I also believe Brumm’s proof. Nice work!

21 July, 2009 at 4:34 pm

partalopoulo238. Continuing post 218.

Applying the induction hypothesis on M’ and A’ we find that there is a permutation t in S_{n-1} so that the partial sums S_j:=a_{t(1)},….,a_{t(j)} do not lie in M’.

We first get rid of 2 easy cases. First, if m’>a_1+…+a_{n-1}, we are done (just choose a_n as the last jump). Second, if m’1 by the induction hypothesis.

So now assume that a_{t(1)}<m'<a_1+…+a_{n-1}. Then there exists a unique k in {1,….,n-2} so that S_k<m'<S_{k+1}. If k+1=n-1, then we are done because m is different from S_{k+1}=a_1+….+a_{n-1} by our assumption. Hence we may assume that k+12 jumps are chosen in order to avoid the points m’ and m, which is possible by the induction hypothesis. This completes the proof.

21 July, 2009 at 7:06 pm

ZachComment 239.

First, I apologize as I haven’t read all the posts here. I thought I might throw in a little idea I have, though.

I think all we need is induction. The base case n = 1 is easy, and if we suppose it’s true for $n = k$ and we’ve got a sequence $(a_i)$ of $k + 1$ distinct positive integers and a set $M$ of $(k+1) – 1 = k$ positive integers, then to apply the induction hypothesis just remove an element of $M$ (any element will do), calling the result, say, $M’$, and then find an element of the sequence to remove such that the sum of the smaller sequence isn’t a member of $M’$. Once this is done, the induction hypothesis will apply to the smaller sequence and $M’$, and I think the problem can be solved from there.

Showing this latter (that a suitable element of the sequence can be removed) I suspect is just a counting argument.

21 July, 2009 at 7:12 pm

Kristal Cantwell239.

Brumm’s proof case 4(There is a spoiler warning):

“max a is not a mine and f=0. As in case 3, construct M’, jump max a first and solve for the remaining a_i and M’. If this solution hits min M in step k, construct a new solution by exchanging step k+1 and step 1 (i.e. max a). There are no mines before min M, thus the mine is avoided and no new mines are hit. We have completed solution for n+1

I hope that’s it and it’s shut tight. This problem is just evil”

What if solution jumps over min M and hits a larger element of M then couldn’t the exchange hit the the original element min M or for that matter any smaller elements of M it has jumped over before hitting the mine?

21 July, 2009 at 7:26 pm

jc239.1

The solution for the {a_i}\max a with mines at M’=M\min M is guaranteed to exist (and hence not hit any element of M except possibly min M) by the induction step for grasshopper problems of size n.

Forgive me if I misinterpreted your comment.

21 July, 2009 at 7:49 pm

brummNot sure I understand you. The solution (solves for M’) hits by definition no other mines in M, because the induction assumes all problems of size n are solved successfully.

A technicality: When solving the smaller problem from some starting point like max a, of course the numeric values of the mines in M’ have to be reduced by starting point, I.e. A=(1,5,10,11), M=(12,13,14), max A=11, A’=(1,5,10), M’=(1,2,3)

Thanks for the kind words. Actually I saw the key idea (isolating max a and min M then solving by recursion) in a faulty proof which only considered cases 3, 4 and which seemed to assume that you can “extend” M_n to M_n+1. I wrote it up mainly to have a full documented proof with URL. Acquaintance got faulty proof from mathlinks.ro dicussion I believe. Have to admit I didn’t get that all of that idea on my own. I tried induction over the hopper jumps and exchanging with earlier jumps if a mine is hit – this turned out to melt my brain but got no results. Considered combinatorics, the n! hopper jumps are all different from each other in at least one jump position, but this went nowhere either. Then the idea of finding the “biggest clump” of mines and bridging it first with max a was considered, this doesn’t work either. It’s surprising how easy it looks in the full proof, especially case 4 (mines cluster in the middle) which had been a nightmare in previous attempts.

21 July, 2009 at 7:24 pm

Kristal Cantwell240.

from 239.(There was a spoiler warning from the original)

“What if solution jumps over min M and hits a larger element of M then couldn’t the exchange hit the the original element min M or for that matter any smaller elements of M it has jumped over before hitting the mine?”

No it can’t do that because we have solved for the remianing a_i and M

so it looks like it works.

21 July, 2009 at 11:20 pm

Curioso241. I have an alternative step for use in induction on the number of intervals.

Assume a sequence of n intervals cannot be blocked by any set of n-1 mines.

Construct a set of n mines that will block this sequence of intervals.

Then the longest path that is blocked must terminate on the last mine, because we know that we can cross any sequence of n-1 mines by assumption.

Next step would be to show that we can unblock by adding another interval to the sequence.

21 July, 2009 at 11:56 pm

Mark Bennet242

I was not quite sure about the fourth of Brumm’s points. If I put all the mines near the end, I can force the last jump to be any particular one of the Ai. Does the induction pick out the right one?

But thinking about it, it seems to be delicate enough to do it rather nicely.

22 July, 2009 at 12:06 am

partalopoulo242. I think I finally figured out what is going on with my posts (after reading the “about” page of the blog). Whenever I used two signs of strict inequalities (one less than and one greater than) the text that lied between them disappeared because the site interpreted them as html code.

Rewriting post 238:

Applying the induction hypothesis on and we find that there is a permutation so that the partial sums do not lie in .

We get rid of two easy cases. First, if , we are done (just choose $a_n$ as the last jump). Second, if , then pick as the first step and then choose the next steps by possible rearranging and in order to avoid the point . This can be done by the induction hypothesis.

So now assume that . Then there exists a unique so that . If , then we are done because by our assumption (choose as the last jump). Hence we may assume that jumps by possibly rearranging and in order to avoid the points and , which is possible by the induction hypothesis. This completes the proof.

22 July, 2009 at 12:39 am

Curioso245. Alternative complete proof

We restrict ourselves to to sequences of intervals in ascending order; this is without loss of generality.

Assume a sequence of n intervals cannot be blocked by any set of n-1 mines.

Pick any sequence of n intervals and add a new interval greater than all the others.

Any set of n mines that blocks this new sequence, must also block the original sequence of n intervals; otherwise we could just take an unblocked path from the original sequence and append the new interval, contradicting that this set blocks the new sequence.

The longest path blocked in the original sequence must terminate in the last mine (by 241). Exchange the last interval in this path with the new interval that has been added (which must be greater and just jumps over the mine), and we have unblocked the path. remaining intervals can just be appended to reach the target, because we have passed the last mine.

So any sequence of n+1 intervals cannot be blocked by n mines assuming we cannot block a sequence of n intervals with n-1 mines. We cannot block a sequence of 2 intervals with 1 mine, so by induction we have proven al cases.

22 July, 2009 at 5:09 am

David Speyer“The longest path blocked in the original sequence must terminate in the last mine (by 241).”

Let the intervals be .

What if there is a mine at , and also a mine at some value greater than this? Then your original sequence will terminate at , which is not the last mine. The reason the induction does not apply is that the inductive set up has an assumption that there is no mine at the sum of the intervals.

This is why Brumm's argument needs cases 1 and 2. Your argument is the reflection of Brumm's cases 3 and 4.

22 July, 2009 at 5:14 am

David EscottI don’t think this works… You have correctly proved that if M is a minimal blocker of A (meaning you cannot remove any mine and still block), then M does not block A’=A union a_max. If you want to have a set of mines that blocks A’ with M as a subset then you would have to add at least one mine, but I don’t think that shows that a rearrangement of M would not block A’.

22 July, 2009 at 5:17 am

David SpeyerMy previous message was eaten by the spam filter. My current theory is that it has a very bad method of counting links and eats any comment with too many less than or greater than signs. So I’ll try again without them:

Let the lengths of the intervals, written in increasing order, be a_1, a_2, …, a_n. Suppose that there is a mine at t=a_1+a_2+…+a_{n-1} and also a mine at u, for some u greater than t.

Then your inductively constructed sequence of jumps will be blocked at t, which is not the largest mine.

This is why Brumm’s argument needs cases 1 and 2. Your argument is basically the mirror image of cases 3 and 4.

22 July, 2009 at 5:22 am

David EscottI take back my previous… I think this can work.

Assume A not blocked by M when |A|>|M| proved for |A|a_i in A.

If M’ blocks A’ then M’ blocks A, otherwise a_1…a_n,a_{n+1} reaches the end.

Since M’ blocks A there exists an M subset of M’ where M is a minimal blocker of A.

Therefore a path in A reaches the last mine im M.

Exchange a_{n+1} with the a_k which hits this mine to avoid it.

Therefore M cannot block A’.

But M’ does block A’, so M’ must be strictly greater than M.

22 July, 2009 at 5:24 am

David EscottTypo..

A not blocked by M when |A|>|M| proved when |A|a_i in A.

If M’ blocks A’ then M’ blocks A, otherwise a_1…a_n,a_{n+1} reaches the end.

Since M’ blocks A there exists an M subset of M’ where M is a minimal blocker of A.

Therefore a path in A reaches the last mine im M.

Exchange a_{n+1} with the a_k which hits this mine to avoid it.

Therefore M cannot block A’.

But M’ does block A’, so M’ must be strictly greater than M.

22 July, 2009 at 5:25 am

David EscottTerry…. please get a wiki this is annoying!!!

A not blocked by M when |A|>|M| proved when |A| less than or equal to n

Take WLOG A’=A union a_{n+1} where a_{n+1}>a_i in A.

If M’ blocks A’ then M’ blocks A, otherwise a_1…a_n,a_{n+1} reaches the end.

Since M’ blocks A there exists an M subset of M’ where M is a minimal blocker of A.

Therefore a path in A reaches the last mine im M.

Exchange a_{n+1} with the a_k which hits this mine to avoid it.

Therefore M cannot block A’.

But M’ does block A’, so M’ must be strictly greater than M.

22 July, 2009 at 5:34 am

Curioso@David Escott: I say that if a set of mines blocks A’, then it must also block A. If it does not, I take an unbocked path of A and append a_max, which wuld also be unblocked, contradicting the assumption that tis set of mines blocks A’.

@David Speyer: If there is mine at u greater than t, then u cannot be reached in the original sequence, and n-1 mines cannot block the original sequence by the induction assumption.

22 July, 2009 at 5:50 am

Mark BennetI think this nearly works. Assume that I can do the case with n (M, s etc). I therefore can jump any set of n-1 mines with a set of n distinct jumps.

I want to do the case for n+1. I remove the longest jump, leaving me with a distance s’ I can jump with the remaining ones.

Curioso’s point is that, because I can make sure I jump n-1 mines with at most n jumps, the only way of blocking my n jumps with n mines is for me to land on the last one.

But I’ve taken out the longest jump, so I replace the jump which landed on the last mine, with the longest jump, which definitely clears it, and there are no mines left to obstruct the rest of the path.

It looks nice and nearly works, but doesn’t take account of the fact that a mine at s’ acts as a blocker, and there may be other mines beyond it – ie the cases with a mine at distance max a from the far end.

22 July, 2009 at 6:12 am

David EscottDavid Speyer,

I am convinced this works… when restricting from A’ to A, you also need to restrict your blocking set. If M’ blocks A’ then M’ blocks A, therefore you can find a subset M of M’ which blocks A which is minimal (nothing can be removed). Curioso then shows that this M doesn’t block A’, but that implies that M is not equal to M’, so M is a strict subset of M’, and |M’| is strictly greater than |M|, which completes the induction hypothesis.

22 July, 2009 at 6:19 am

David SpeyerTake A = (1,2,3,4) and M = (6,7,8). The induction, as proposed, is to consider A’ = (1,2,3). No matter how we order A’, this jump sequence is blocked at 6, which is not the largest mine.

22 July, 2009 at 6:25 am

Mark BennetIn terms of Brumm’s solution, the case this doesn’t deal with is the first case.

If the longest leap doesn’t hit a mine, this is simple and elegant.

If the longest leap first or last jumps no mines but hits one, solve the remaining part as if this mine is not there, replace the end leap which hits the mine with the longest one to clear it and we’re done – this idea is in Brumm and Curioso.

It is if the longest leap jumps at least one mine and lands on a mine there is a problem (at either end of course, and don’t forget that the longest leap can be greater than the sum of all the others, or equal to the sum of all the others, in which case this is the same mine both times). If a shorter leap jumps a mine and lands clear the induction follows.

22 July, 2009 at 6:39 am

Curioso@Mark Bennet: You are right. It is not a problem if the blocking set has a mine at s’ and no mines beyond that, the reasoning still works then, but I overlooked the case where there are mines beyond s’.

22 July, 2009 at 1:02 am

Mark Bennet246

Ref 245 – it is possible to begin the induction with the trivial observation that you can’t block one interval with no mines.

22 July, 2009 at 1:04 am

CuriosoTrue

22 July, 2009 at 1:22 am

Mark BennetBut I should have added – it looks very neat.

22 July, 2009 at 5:35 am

David EscottCurioso’s proof got me thinking along a line that might provide some kind of classification of the structure of the mines.

M minimal blocking for A

|M|=m |A|=n

m_m last mine in M

Exists path a_1,…a_k that hits m_m and no other mine.

a_k gt a_{k+i} for i gt 0. Otherwise swap a_k and a_{k+i} to escape.

Each of a_1+…+a_{k-1}+a_i is mined. Otherwise swap would escape.

That accounts for k mines related to the tail, that all must occur within a_k of the last mine. Can these be separated from the head in some way? Can we prove that all mines must occur within a_k of the last mine, or is there a ready counter example.

Among the truths to work with:

a_1+…+a_{k-1} is not mined.

Each path a_1…a_{i-1},a_k,a_{i+1},…a_{k-1},a_i hits a mine, at some point.

22 July, 2009 at 6:40 am

Mark BennetDavid

If you are using the Ai equal (1,2,3,4 … n), then you can hit the last mine of a block of n-1 near the end by using the jump (n-1), but you need to use jump (n) to clear it. You have to deal with the case where you’ve used (n) near the beginning.

22 July, 2009 at 6:52 am

David EscottThe a_i are ordered by how they appear in the sequence, not by magnitude. In the case you describe a_1=a_k=n, and the statement that “Each of a_1+…+a_{k-1}+a_i is mined. Otherwise swap would escape.” means that 1…n are all mined.

I know its not helpful to be this terse, but the spam blocker keeps causing problems.

22 July, 2009 at 6:39 am

robertNot easy to follow this series of comments; not helpful for someone like me with lesser math ability though i am very keen to know. Has anyone among those commenting solved it? and if so, can someone please post in one entry the complete “user friendly” proof? Thanks.

22 July, 2009 at 7:19 am

Mark BennetWARNING

This is a version of Brumm’s proof with inspiration from Curioso.

We are trying to find a path for a grasshopper through a minefield. The grasshopper has n distinct leaps of length ai (i = 1,2 .. n). The minefield contains n-1 mines, has length s (the sum of the ai), and no mine in the last place.

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the largest leap.

Case 1: If the largest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the largest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

If this arrangement also avoids the mine we removed, we are done. If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the largest leap lands on a mine but doesn’t jump any mines, this is similar to case 2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine. We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: the longest leap lands on a mine and jumps one or more mines. Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.

We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.

Observe there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.

For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.

This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

22 July, 2009 at 7:31 am

Mark BennetI should also say that the ai are all greater than zero.

22 July, 2009 at 7:53 am

Mark BennetObservations on solution

Note that this solution uses two main techniques.

If we jump a mine using the longest leap, we use the inductive hypothesis for one fewer or two fewer mines, depending on the case.

If we don’t jump a mine using the longest leap, then we use the inductive hypothesis differently, from the other end of the minefield, and when we reach a block we use the fact that we have the longest leap spare to clear it.

It is not always true that the longest leap jumps a mine (the easy part of case 2), and it isn’t true that this solution puts the longest leap as close to the beginning as possible. The more difficult part of case 2 requires a short leap to be replaced by the longest leap. If there happened to be another long enough leap available, this could be used instead. The proof could be tidied up to force the longest leap closest to the beginning, by applying the harder part of case 2 only when there is no path for the easier part.

Only the hard part of case 2 can force the longest leap out of the first two places, so this is unavoidable since I can force the longest leap to be anywhere I choose for the jump set (1,2 …n) by putting all the (n-1) mines together.

Cases 2 and 3 require the longest leap to be different from another leap so they can be exchanged, and case 4 requires shorter leaps to be distinct for the counting to work.

22 July, 2009 at 8:53 am

Mark BennetSome questions

1 Whether it is possible to classify the cases in which the longest leap cannot be one of the first two in some simple way.

2 Whether it is possible to reduce the number of cases which have to be considered. Cases 2 and 3 are very similar, for example.

3 Whether the counting argument in case 4 can be eliminated, or alternatively extended to cover other cases. It seems that case 4 – strangely, since it is the one which engages with most mines most quickly – is the part of the argument which is hardest to see.

22 July, 2009 at 9:01 am

John SidlesThe above solution was lots of fun to read!

It suggests the following (stronger) conjecture—a conjecture that might perhaps lead to alternative proof.

We are given a grasshopper jump-set and a mine-set. We know that there is a least one path-ordering of the grasshopper jump-set that misses all the mines. So if we consider the set of all path-orderings, we know that the fraction

fof paths that hit at least one mine is strictly less than unity.We conjecture that if we add one more jump to the jump-set, and one more mine to the mine-set, then

fdecreases.Is this (stronger) conjecture true? If so, can it be proved by (perhaps non-constructive) combinatoric arguments? This might lead to a more Tao-esque proof of the original theorem.

The point is, that oft-times when a proof is achieved, the fun is just beginning! :)

22 July, 2009 at 9:23 am

Mark BennetA similar conjecture might suggest that f decreases as s (the length of the minefield) increases, keeping n the same.

22 July, 2009 at 10:12 am

a.s.The conjecture seems to be false. Take A={1..n}, M={2..n}. Clearly, there are (n-2)! paths that miss all the mines. This appears to be “most efficient” minefield (can be easily checked for small n). In this case, f=1-1/(n(n-1)) and it increases to 1 as n goes to infinity.

22 July, 2009 at 11:28 am

Kristal CantwellIf you have a a set of jumps such that all jumps and sums of jumps miss all mines and then add a mine that hits one of the initial jumps and an arbitrary jump then the f will not decrease and in fact it will increase.

22 July, 2009 at 12:50 pm

Mark Bennet253

I still haven’t quite worked out what partalopoulo has been trying to post as a solution, and how it relates to brumm’s.

22 July, 2009 at 1:05 pm

Mark Bennetsorry 253 was in the wrong place – my browser is playing up.

What I wanted to say here to Kristal is that it is trivially possible to do such a thing eg if all our jumps are even, and the mines are all in odd places.

However there may be some more sophisticated version of measure taking n and s as parameters. eg for a particular minefield of length s with n-1 mines take the fraction of (paths through the minefield)/(all possible paths ignoring mines) over all possible jump sets with n jumps. Or do the same over all minefields of length s with n-1 mines. These average out the special cases.

The question is whether this is at all useful – and whether the special cases create the conditions for density increment/decrement as in the original polymath, and whether this goes anywhere, and whether there is an interesting two- (r-) dimensional generalisation.

As s increases, the density of the mines decreases, and intuitively there ought to be, on average, more flexibility about getting through. Indeed there are only a maximum 2^n possible places which can be hit by any subset of the jumps, so as s increases above 2^n there is more chance of mines being in places which can never be hit by the grasshopper.

But i would be interested in generalisations to more than one dimension.

22 July, 2009 at 10:59 am

Curioso250. (skipping some unnumbered comments)

I wonder if the complement of this theorem is also true, i.e. can any sequence of n leaps be blocked by n mines.

Insight in this may give insight in the proof we have here, and may give opportunity to simplify it still a bit (I think the counting for case 4 is central to the proof).

22 July, 2009 at 11:05 am

Kristal Cantwell251.

in regards to 250 couldn’t you use the n initial jumps as blocking mines and block any sequence by blocking the first step?

22 July, 2009 at 12:17 pm

jc252. I’ve written up a quick and dirty implementation of Brumm’s algorithm in Mathematica. A “pastebin” of the code is in my website link.

22 July, 2009 at 1:08 pm

Kristal Cantwell253.

There is a dual form of Bramm’s proof. it based on the fact that we can subtract everything from the sum of the a_i’s and get a copy of the same problem with roughly what happens is that you can replace max a with

target-max a and let f be the number of mines targe-max a and target.

I have just lost my write up of the complete proof in the one of the filters I suspect the spam filter perhaps.

22 July, 2009 at 1:13 pm

Kristal Cantwellhere is my second attempt at case one of the dual of Bramm’s proof mentioned above

max a is a mine and f is greater 0. In that case, out of the target-a_i that are not max a (n numbers), at least n-f are not mined (when taken as a first jump). Consider the n double jumps (target–max aa_i != max a, target-max a target). At least n-f of those are not mined on first jump. The number of mines in (0 target -max a) is the number of mines (n) less f less the one for target -max a, yielding n-f-1 which is less than n-f. Thus by counting argument, at least one of the double jumps does not hit a mine on both jumps. This double jump takes two jumps and jumps over f+1 >=2 mines, yielding a problem with n-2 mines and n-1 remaining jumps, which is solved by induction.

22 July, 2009 at 1:22 pm

Kristal Cantwell255. second step of dual of Bramm’s proof

target-max a is not a mine and f>0. Take max a as last jump, yielding problem with n remaining jumps and n-f<n mines, which is solved by induction.

22 July, 2009 at 1:28 pm

Kristal CantwellThird step of dual proof:

target- max a is a mine and f=0. Let max M be the largest mine in M. Construct M’=M\{max M}. Jump target-max a to target as the last jump and solve the n-problem with the remaining a_i and M’ Let a_x be the last jump of this solution. Exchange max a and a_x (i.e. jump a_x last and max a before that). target -(max a+a_x) is no mine (guaranteed by solution), target-a_x is no mine (because target-a_x is greater than target-max a == max M as above). There are no mines in the rest. We have completed solution for n+1.

22 July, 2009 at 1:35 pm

Kristal Cantwell256, Final case of dual proof

target-max a is not a mine and f=0. As in case 3, construct M’, jump max a last and solve for the remaining a_i and M’. If this solution hits max M in step k, construct a new solution by exchanging step k-1 and the last step (i.e. target-max a). There are no mines after max M, thus the mine is avoided and no new mines are hit. We have completed solution for n+1

22 July, 2009 at 5:28 pm

Terence Tao257. I should have done this earlier, but I have opened up a wiki page for this project (borrowing space from the polymath1 wiki) at

http://michaelnielsen.org/polymath1/index.php?title=Imo_2009_q6

In it I have recorded my own proof of the problem (as Proof #1); it would be good to have the other complete proofs up there as well.

22 July, 2009 at 6:49 pm

Pietro Poggi-CorradiniLine 10 of Proof 1 in the wiki: “and suppose that the grasshopper is already known to be immune to order 1″ should that be j?

[Corrected, thanks – T.]22 July, 2009 at 7:26 pm

Kristal Cantwell258.

I looked at proof #1 in the wiki I think I might be able to find a dual for it the same way in posts 253 to 256 I found a dual for Bramm’s proof. I think mosts proofs would have duals.

22 July, 2009 at 10:12 pm

Daniel MoskovichI just saw the thread… beautiful proof, actually- like any good proof, it looks obvious after you’ve seen it (although not before).

I wonder what the generalization would be to other lattices. So you would be allowed to move units along the lattice, and the goal would be to hit any point at distance $\latex a_1+a_2+\cdots+a_n$ from where you started. How many mines would it take to block you?

Of course there are many other generalizations possible… one might wonder what happens if one restricts to lattices consisting of integer points in , or allow only certain moves (only in straight lines, or something).

I also wonder whether there is a continuous version of the problem, although I have no idea what it might look like.

23 July, 2009 at 1:30 am

Daniel MoskovichMaybe in fact the natural generalization is to consider graphs, and one is allowed to jump units along the graph. The objective is to reach any vertex at distance $a_1+\cdots+a_n$ from the initial point (Q6 corresponds to the graph with vertices with 2 vertices of valence 1 and all other vertices of valence 2). This encapsulates all generalizations considered so far (I think, unless somebody has mentioned this already).

23 July, 2009 at 9:03 am

Kristal CantwellIf there were a single objective vertex and a transformation T interchanging the starting vertex and the objective vertex while preserving the structure needed for the problem then the transformed problem would be the dual problem and each step of the proof S would have a dual step

TST^-1 thus giving a dual proof.

25 July, 2009 at 7:59 am

Daniel MoskovichKristal Cantwell:

I can always assume that the number of terminal vertices is 1 by identifying them. For a graph which admits an involution which exchanges the initial and terminal vertex, you and invert the solution… perhaps these are the only graphs for which the problem is interesting.

The 2-dimensional case seems the first to tackle- get to distance from (0,0), where you can move $a_1,\ldots,a_n$ units along the lattice. There are some silly trivial upper bounds on the number of mines which would block the grasshopper, but I don’t know the actual number, much less how to prove it…

23 July, 2009 at 3:32 am

Curioso259. I am still trying to simplify the proof.

We have a set of n jumps a_i and a set of n-1 mines m_j.

Let s be the sum of the a_i.

Assume we have a blocking set of n-1 mines m_j.

Then we can take out an a_i such hat there is no mine at s-a_i (because there are more a_i than mines), and take out the last mine. Now these reduced sets must still be blocking, otherwise we could just take an unblocked path, add back the mine (which is not at the final point of the path), and add the jump we have removed.

So by induction the blocking set of n-1 mines cannot exist.

23 July, 2009 at 3:59 am

brummI think you keep slipping into the same hole again and again. There’s no need for the mines to behave nicely, they can cluster as they want.

In your case consider A=(5,6,7), s=18, M=(16,17). You take out the mine at 17 but the mine at 16 does not block A=(5,6).

23 July, 2009 at 5:48 am

Curioso@Brumm: But mines 16,17 are not blocking the jumps 5,6,7.

But I see the problem, you cannot just put back the mine, it might be somewhere else on the path..

23 July, 2009 at 3:56 am

ajSince I lost out on coming up with a proof, I thought it’d be fun to redo Bramm’s proof as a program, which I wrote up on my blog. While I was writing the code, a few of the cases collapsed, making, I think, for a potentially nicer proof.

I think it should be plausible to do just two cases: where min(m)<max(a) and max(a) is mined; and where you can rearrange the path for the smaller problem (a-max(a),m-min(m)) (label that path as p), as x,max(a),y, where p=y+x and x is the first step in the path after min(m).

23 July, 2009 at 6:13 am

Mark Bennetaj

You might want to add this comment to the wiki, with the link – I put in a link to your program.

23 July, 2009 at 5:42 am

Ralph HartleyOK what happens if we remove the constraint that the a_i (and M) all be positive?

Under what condition is there a solution with m mines?

23 July, 2009 at 6:10 am

Mark Bennet262 Reply to Ralph Hartley

Are you allowed to step outside the minefield on your path? Can you go beyond the end and come back, or jump onto negative integers.

Query where are you placing your mines – can they go on negative integers or beyond point s?

23 July, 2009 at 6:41 am

Luka Lasicind. proof of question 6. IMO

def. S_{k} = Sum of every a_{i } excluding only one a_{k}

Clearly, exists S_{k} which is not in M.

Induction step on A’ := A \ { a_{k} } and M’ := M \ { m_ {i} }

leads to solution with a_{k} on the last place.

23 July, 2009 at 7:21 am

aj@Mark Bennet 6:13am; written up and added to proof page! What fun!

23 July, 2009 at 7:42 am

CuriosoThis sounds the same as what I tried in 259. This fails because you cannot put back m_{i} with the guarantee that the sequence of jumps for A’ does not land on it, at least I do not see that guarantee.

23 July, 2009 at 8:22 am

Kristal Cantwell264.

I have added the dual of Bramm’s proof to the wiki. I think most proofs will have an associated dual.

23 July, 2009 at 9:01 am

Luka Lasic@Curioso In induction step A’ is fixed, but M’ has free choise of

on the term m_{i} ( excluded from M ).

23 July, 2009 at 9:28 am

CuriosoYou have a solution for A if m_{i} > S_{k}. But what do you do if m_{i} < S_{k}, i.e. how do you make sure it is not on one of the jumping pints of the solution for A'?

23 July, 2009 at 10:40 am

Pietro Poggi-CorradiniPossible variant to proof 1: redefine “immune of order j” to mean that there exists a given subset of the a’s with j elements that can be re-odered so as to avoid the n-1 mines. Now assume that no subsets with j+1 elements is immune. By induction hypothesis there is one subset with j elements that is immune (and ends say at s_j). Extend it using one of the remaining n-j jumps. They all land on mines, meaning that there are n-j mines to the left of s_j, but doesn’t this contradict assumption A in reverse. I might be doing something wrong.

23 July, 2009 at 7:10 pm

Terence TaoDear Pietro,

The n-j mines are to the right of s_j, rather than to the left. But the more serious issue, I think, is that we don’t know that the grasshopper can safely reach s_j in n-j steps from the right, rather than from j steps on the left, so the dual of Assumption A does not seem to apply here.

It is instructive to see what happens when and the blocking set M takes the form for some medium-sized r. Then it’s quite possible to reach r in a manner that uses up the n jump, and then get stuck, without any obvious violation of Assumption A or its dual at this point. One has to take a more “global” view and look at all the possible places the grasshopper can reach in j steps at once in order to see the Assumption A violation.

23 July, 2009 at 10:06 pm

pietropcThanks and sorry for the typos in my previous comment. I finally understand Proof 1, I think. You might want to state explicitly that : this seems to be crucial to keep disjoint from . Finally a small quibble, in line -3, "by Assumption A" should this be "by induction hypothesis"?

23 July, 2009 at 12:12 pm

IMO 2009 Q6 mini-polymath project: impressions, reflections, analysis « What’s new[…] | by Terence Tao The mini-polymath project to find solutions to Problem 6 of the 2009 IMO is still ongoing, but I thought that, while the memories of the experience are still fresh, it would be a good time […]

23 July, 2009 at 9:10 pm

Abhishek Ghose267.

Unfortunately, I am seeing this problem very late (I stumbled across this blog only yesterday). I had a quick thought regarding this, and I could only give a cursory glance over at the comments (given their now huge number – things probably work out better if you’re involved from the start :) ). The post by Richard(117) seems to be quite close to what I have in mind.

For every possible permutation of {a0,…,an}, we define a conflict set as one containing all the numbers in the number line the grasshopper steps on when following this particular stepping order/permutation. Clearly, if M contains at least one element from some conflict set, the corresponding permutation is unusable. For all possible permutations to be unusable M must contain at least one element from the conflict sets of each of these permutations. If we can prove that the minimum possible size of such an ideal M (that renders every permutation unusable) is greater than n-1, we are done.

The tricky part, of course, is to find the minimum sized M. Especially, since some ‘conflict elements’ might be common across different permutations.

23 July, 2009 at 9:15 pm

Abhishek Ghose(Missed copying the last sentence from my text editor :) )

Pigeonhole or Induction for finding the minimum size may be viable approaches?

23 July, 2009 at 9:49 pm

Terence Tao’s polymath experiment « Mathematical Remarks[…] Terence Tao’s polymath experiment Published July 24, 2009 Uncategorized Leave a Comment I’m having fun following this. […]

24 July, 2009 at 12:58 am

Mark BennetI’ve put some comments on the proofs in the discussion part of the Wiki – do add comments and correct errors.

24 July, 2009 at 7:53 am

JuanHi!

I don’t understand Tao’s proof. More specifically, I don’t get the last sentence “But this forces M to contain n distinct elements, a contradiction.”

Can anyone elaborate the point a little further for me, please?

24 July, 2009 at 7:57 am

Alex and EckiWe looked at proof #1 and have an additional suggestion to pietropc’s suggestions in his post: in the last paragraph one should chose i as the greatest element rather than smallest (or change to ) to ensure that all the following numbers are distinct from each other.

It might be nice to make the three groups of numbers that lie in M which are n numbers in total more explicit: 1. for , 2. for and 3. for the biggest the numbers .

24 July, 2009 at 2:16 pm

Terence TaoThanks for all the corrections and suggestions! I’ve updated the proof accordingly (but of course you are welcome to make future corrections directly, if you wish).

24 July, 2009 at 8:10 am

Kristal CantwellHere is another proof. We remove the largest mine and the largest step a_max. We apply induction. Two things can happen we hit the largest mine or we reach the sum of all the a_i’s(target) minus the largest step a_max. If we hit the largest mine we swap the last step for the largest step and we skip over the largest mine then we just continue till we are done. If we go to the the sum of all the a_i’s except the largest step and it is not a mine we add one more step and we are done. If it is a mine and we replace the last step with a_max and we don’t land on a mine then we take one more step then we are done.

We have one case left where target – a_max is a mine and there is one or more mines greater than target – a_max call the number of these mines f.

Then what remains is case one of the dual proof which we solve as follows:

max a is a mine and f is greater 0. In that case, out of the target-a_i that are not max a (n numbers), at least n-f are not mined (when taken as a first jump). Consider the n double jumps (target–max aa_i != max a, target-max a target). At least n-f of those are not mined on first jump. The number of mines in (0 target -max a) is the number of mines (n) less f less the one for target -max a, yielding n-f-1 which is less than n-f. Thus by counting argument, at least one of the double jumps does not hit a mine on both jumps. This double jump takes two jumps and jumps over f+1 >=2 mines, yielding a problem with n-2 mines and n-1 remaining jumps, which is solved by induction.

25 July, 2009 at 8:57 am

Kristal CantwellI just added this to the wiki.

24 July, 2009 at 8:16 am

JuanThanks, Alex & Ecki! Now I get it. It’s a beautiful proof!

24 July, 2009 at 10:38 am

Mark BennetIf I have a set of positive integers {A1 … Am} sum Sa and another {B1 … Bn} sum Sb (Ai distinct, Bj distinct), a jump in a two dimensional space involves moving (Ai,Bj), I start at (0,0) and there is no mine at (Sa,Sb) – what is the minimum number of mines I need to block.

(maxA x maxB) can block by putting a rectangle starting at (1,1). Can I always dodge (MaxA x MaxB)-1?

This looks rather easy, for example, I can avoid some rectangles of size (MaxA x MaxB) entirely.

Further dimensions diminish the density of the mines. So is there an interesting generalisation?

26 July, 2009 at 12:53 pm

Kristal CantwellIf the sums are distinct then it looks like you need all nxn mines or in k dimensions n^k so if you don’t need nxn points in all cases the number you need will depend on whether the sums are distinct. I don’t know of a counterexample requiring less then nxn mines. The problem looks interesting.

24 July, 2009 at 9:01 pm

Pablo LessaIn the end I couldn’t help myself and had to follow through on the study of the special case $A = \{1,2,\ldots,n\}$.

In the case $n$ odd, the pigeonhole principle provides at least one residue class modulo without landmines. I was able to prove that there is a path that steps on each point of one of these “safe” residue classes (in the interval $0,n(n+1)/2$ of course) while avoiding all landmines.

In the case $n$ I use instead a “safe” residue class modulo $n+1$ and obtain the same result.

The proof was based on dividing the jumps into pairs adding up to the same number, and asigning a different pair of jumps to each of the intervals between the elements of the safe residue class. There is a simple counting argument that shows that this can be done.

24 July, 2009 at 11:59 pm

Mark BennetPablo

I think you may be assuming that the jumps are {1,2 … n-1}, which seems to be the toughest case.

If the jumps are {1,2,4 …. 2^(n-1)} there are no two pairs with the same sum.

26 July, 2009 at 2:26 pm

Pablo LessaI’m assuming exactly that.

The point is that in that case there is a different proof that exploits the fact that there are many ways of obtaining the same sum.

In fact, one may view the argument as being based on (in the even case… in the odd case it would be ).

The result seems to show that an apparent disadvantage (i.e. a single mine can block many paths) may actually be an advantage (i.e. we can find a solution that fulfills the aditional restriction of touching all points in a certain residue class).

25 July, 2009 at 2:00 am

Mark BennetAre there any thoughts on the best approach for a grasshopper who can detect whether the next jump will land on a mine, and can count the number of mines passed – are there efficient algorithms for getting through the minefield?

25 July, 2009 at 6:42 am

CuriosoYou cannot determine a safe path for the grasshopper based on local information only, you need to take a global view. Let s be the sum of the a_i, put the mines on s-a_1, s-a_2 … s-a_n, except for one place s-a_i that you leave empty. The grasshopper does not know which a_i until it makes the jump into the minefield, but then it is not certain that it still has a_i available to jump over the rest.

25 July, 2009 at 8:08 am

Mark BennetSo the grasshopper is allowed to backtrack.

The answer will depend on what the grasshopper is allowed to remember.

A brute force search (try everything until something succeeds) will always find any path which exists.

How do these two strategies work out:

1. If I have a choice, always use the longest leap I can

2. If I have a choice, always use the shortest leap I can

In each case, when blocked, backtrack as little as possible for an option, and use the next leap in the list.

In longest leap first, if I encounter a block of r mines, and I am allowed to remember it is there, I can add ‘if I have not passed the block, make sure I have a leap of length at least r+1 in hand.’

In shortest leap first, I keep the long leaps in hand.

There are always ‘bad’ configurations, like the one which forces the last leap by blocking all other possibilities with mines near the end.

Is there a good measure of the effectiveness of a strategy?

25 July, 2009 at 2:05 am

Gil KalaiDoes the problem make sense over a finite field rather than the integers? It looks that the arguments use the order structur of integers.

25 July, 2009 at 9:27 am

Mark BennetI wonder if there are equivalent formulations. Here is one which is not so general as the original, but might be more confusing to solve.

A round table has n(n+1)/2 seats. n boys come in and discover that there are already (n-1) girls sitting at the table. Show that the boys can always arrange to sit down at vacant seats so that the distances between consecutive boys are all different.

26 July, 2009 at 4:00 am

Mark BennetActually there may be proof strategies which are easier in the circular case (identifying the beginning and end of the path) if the grasshopper can start at any vacant space.

For example, the ‘mod n’ kind of proof – there is a residue class completely unused – promises to work quite straightforwardly with this set up.

And there may be counting approaches which benefit from the extra symmetry of the circle.

25 July, 2009 at 11:15 am

wenwenI’ve a proof which seems to be correct. I don’t know if it appeared in the above discussions.

Let be the given positive integers.

Denote and .

Let be numbers the the grasshopper wants to avoid.

Denote .

Induction on . When n = 1,2,3, it's easy to check.

Assume now for , it's true. We want to show that for , it's true.

Case I.

There exists a , such that . So for the pair we can use the induction hypothesis to get permutation of , say to avoid the set . Since , so the permutation of is good.

Case II.

Consider the pair , by the condition, we know that we can use the induction hypothesis to have one permutation of , say to avoid the set . If for any partial sum , it's NOT equal to , the permutation is what we want; if there is a $k$, such that , we switch and to get the following permutation , it works since this switch provides a big jump to avoid every thing at the step.

CaseIII.

In this case there must be a $1<k<n$, such that

We first claim that we can require for , we have .(otherwise, if , we consider the pair to get a permutation of , and take as the permutation we need.)

Now consider the set and it has exactly elements, so there is a , such that . We consider the pair , it easy to see that we can use the induction hypothesis on this set to get a permutation of , then we can take the permutation for .

25 July, 2009 at 4:26 pm

Luka Lasic@wenwen Case I. wonderful, Case II. wonderful,

Case III. wonderful long jump.

Change cases (1,2,3) -> (3,1,2), and X -> M.

26 July, 2009 at 7:37 am

Luka LasicPROBLEM {0,1,2} :

O:={0} and splits are: 0 -> (1,2) and 0->(2,1) and 1->(0,2) and 1->(2,0) and 2->(0,1) and 2->(1,0). Now:

A={(1,2),(2,1)}, and splits on first coordinates leads to:

1[A]={(0,2,2),(2,0,2),(0,1,1),(1,0,1)}, and splits on second coordinates leads to:

2[A]={(1,0,1),(1,1,0),(2,0,2),(2,2,0)}. Clearly, intersection of 1[A] and 2[A] are non-empty.

Recursively, 1[1[A]], 2[1[A]], 3[1[A]], 1[2[A]], 2[2[A]], 3[2[A]],

are pairwise with non-empty intersection, and analogous to infinity.

29 July, 2009 at 6:08 am

Gil KalaiAs some sort of control experiment I asked A. Nili and got this reply (I am not sure if it is identical to argument that was already presented):

Problem:

let a_1,a_2,…,a_n be n distinct positive real numbers,

and let b_1,b_2,…,b_{n-1} be n-1 distinct positive reals.

Prove that there is a permutation a_{i1},a_{i2},…,a_{in} of the

numbers a_i so that all initial sums a_{i1}+a_{i2}+…+a_{ij}

differ from all b_k’s.

Solution:

Proof by induction on n. Trivial for n=1, assuming for n-1, omit

the largest a and the largest b. By induction the remaining a’s can

be arranged so that their initial sums avoid all b’s but possibly

the largest. If the largest is obtained as

a_{i1}+a_{i2}+…+a_{ij}, replace a_{ij} by a_max and put a_{ij}

last (or anywhere after a_max), noting that all initial sums of

at least j a’s are now larger than the largest b.

29 July, 2009 at 6:58 am

Kristal Cantwell“Proof by induction on n. Trivial for n=1, assuming for n-1, omit

the largest a and the largest b. By induction the remaining a’s can

be arranged so that their initial sums avoid all b’s but possibly

the largest. If the largest is obtained as”

the sum of the n-1 elements could also be a landmine in the n-1 case we don’t prove it we have it by hypothesis here we have the sum of n elements cannot be a mine by hypothesis.

In my

24 July, 2009 8:10 am proof I go along those lines and then I have to deal with the n-1 elements issue mentioned above. It can be dealt with. I think it is the fifth proof on the wiki.

29 July, 2009 at 7:58 am

Alex and EckiThis is the easier part 1 of the proof 5 already in the wiki.

30 July, 2009 at 12:44 am

GilHmm, right. I overlooked that…

2 August, 2009 at 9:33 am

A mini-polymath project « Euclidean Ramsey Theory[…] http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ […]

7 August, 2009 at 9:49 am

ESadly I only got to see this problem today and it is seems hopeless to follow the discussion.

I was following a first lead on the problem sitting on my coach which seemed to me like a good one.

I would be happy to hear if this direction was discussed and what you guys think.

Let us first notice that since all the jumps are of distinct size we have n! different ways in which our grasshopper can take his course.

Secondly, a simple observation is that we must have at least two completely distinct paths since if we don’t then we can take an arbitrary path and choose our mines to match it exactly, by the assumption we’ve just made, any other path has at least one step that matches the first path and the theorem is disproven(sorry for my shaky English).

So we now know that we must have atleast two completely distinct possible paths. Obviously showing that we actually got two such paths proves the theorem.

Again, if we assume that we do not have such two paths, than every two paths have atleast one point in common, and with some simple combinatorics it is eazy to see that we get less than the N! possible different paths that we know exist.

My bet is that i’m missing something here. It took me less than an hour to come up with this “solution” while many people whos math talent and experience are superior to mine seem to have struggled with the problem.

BTW, did the discussion move somewhere else or something like that?

7 August, 2009 at 10:01 am

EOkay, I was too hasty

“Obviously showing that we actually got two such paths proves the theorem.”

11 August, 2009 at 6:05 am

JMAnother solution, I think.

Let’s suppose

We make an observation: If we get up to or past with steps, then the

-th step lands on a mine. (To see this, let be the steps

with We can find a jump sequence clearing This jump sequence in fact avoids all mines: With steps we can

only trip up on one of the mines ; the -th step doesnt land on a

mine and goes past This allows us to construct a mine free trip for the original

, which we aren’t supposed to be able to.)

Set By considering numbers with , the observation above tells us that there exists

with Of course, we also have those are in

Now consider the following numbers all : and We can conclude that for some

We now use and to jump steps clearing and This trip doesn't land on any mine: if it did, it can

only be on the -th step (anything before, distance covered is ). On the

-th step it must land on for some

But then

So we have in fact a mine free trip of steps going safely beyond ,

which allows us to construct a solution for the original problem.

That proves the claim.

To finish off, by the claim are all So we must

have We use jumps apart from to go clear mines upto and round off with

12 August, 2009 at 1:23 am

JMApart from the formatting problems, couple of paragraphs seem to have disappeared since my writing and it appearing. The solution should begin with:

Let’s suppose

The soln still doesnt read well, but hopefully there is enough explanation for one to work through.

12 August, 2009 at 1:31 am

JMStill doesnt work; last try before I give up :)

Let’s suppose a_1 < \ldots a_n, m_1 < … m_{k+1}.

12 August, 2009 at 6:23 am

Terence TaoI think what is happening is that the parser is interpreting your < and > signs as HTML. One can fix this by using < and > instead. Alternatively, you can place your solution on the wiki at

http://michaelnielsen.org/polymath1/index.php?title=Imo_2009_q6

17 October, 2009 at 3:42 am

Rajen ShahI’m not sure if I’m missing something here:

There are n! different paths that could be taken (if we forget the restriction imposed by the set M).

Each element of M which is a sum of k numbers from a_1 up to a_n blocks out k!(n-k)! of these paths.

Now if we count up the maximum possible number of paths blocked, it is easy to see we can never block more than n! paths.

Does this not work?

17 October, 2009 at 4:46 am

SpencerHi Rajen,

I haven’t thought about the problem seriously myself but I don’t think that your observation provides a solution unless the sums formed from the a_i’s happen to all be distinct.

‘Coincidences’ between the sums will make it harder. For example, if the first few of the a_i are 3,4,6 and 7, then a mine at 10 = 3 + 7 = 4 + 6, blocks more paths than you have accounted for.

21 February, 2010 at 8:44 am

Bài toán số 6 trong IMO 2009 « Sharing[…] link 3 […]

17 June, 2010 at 10:40 pm

Mark BennetHere is a non-technical version of an early solution, developed for use with a school group.

If n=1 there is one jump and no mines. Easy.

Assume cases up to n-1 are done.

Try to make the longest jump from the left hand side.

Case A: this jump clears at least one mine and lands on an unmined place. Thene the remainder is case n-1 and we are done.

Case B: the longest jump clears no mines, though it may land on one. Remove the leftmost mine, and take out the longest jump. Working from the right, now, we have a case of (n-1) and can make all the leaps in some order, clearing all the remaining mines.

Put back the leftmost mine.

If no jump lands on it, then we can add the longest jump at the left hand end, and we are done.

If a jump does land on it, then working from the right, replace that jump with the longest jump. Now up to the longest jump we have cleared all the mines and the remaining jumps can be added at the left hand end in any order to complete the task.

Case C: the longest jump clears at least one mine, but lands on a mine – so there is a mine at distance equal to the longest jump from the left hand end, with at least one mine to the left of this. Then any combination of two jumps from the left hand end and including the longest will clear at least two mines.

Consider the n-1 possibilities (from the left) of {short jump followed by longest jump}. None of these lands on the mine whose fixed position is known – so there are just n-2 more mines to avoid. Because the short jumps are all different lengths, all the positions landed on by this set of n-1 pairs are distinct. n-2 mines can only block n-2 of these possibilities, so there is at least one pair {short jump followed by longest jump} which does not land on a mine and which clears at least two mines. The rest is case n-2 and we are done.

15 August, 2010 at 3:30 pm

nonameI found a solution but it seems too much simple compared to other solutions so please let me know if I made a mistake.

Let S={A_1,…,A_n+1} and T={B_1,…,B_n}

Suppose the statement is true for n. We will prove it for n+1.

Let a k-sum to be sum of k elements of S. Now there are n+1 n-sums and each one is different from one other because elements of S assumed to be distinct. So at least one of the n-sums is not an element of T. Let A_k is not in this n-sum. Apply the statement for S/A_k and T/B_n . Grasshopper doesn’t land on any mine including B_n. By adding this order A_k we prove the statement.