Did they really consider this hard enough for a problem 6??

Well, as far as I know, many strong contestants did not solve it (maybe no italian, british, romanian, french...one german...) thus I guess the answer may be affirmative. Pierre.

lol... looks like #3 and #6 are of similar flavor this year... For this problem, can't you just

I'm not sure if I understand this part of your argument: probability1.01 wrote:

Okay, so I have a sequence that doesn't reach $ M - \{m\}$. But when I change one of the middle hops to be of length $ a_n$, why should I expect the sequence to keep that property? (EDIT: Ah, I missed that $ m$ was largest, as kdano pointed out.)

probability1.01 wrote: lol... looks like #3 and #6 are of similar flavor this year... For this problem, can't you just

I was just about to type my solution that's basically the same, and i couldn't find a bug in it either.

probability1.01 wrote: For this problem, can't you just

It seems like you can, if you missed something, so did I when reading your solution. Actually, I was trying along a similar line as you, but got stuck

I would like to know whether the shortlist contained any problems harder than #3 and #6, I guess I will have to wait for one year... In last year's shortlist, after looking through it, I consider problems A6 and C6 harder than the actual problems #3 and #6 from last year. I also think that A6 was quite original for a functional equation, and C6 a very beautiful problem, probably the most beautiful in the entire shortlist (working on it, haven't still got much). Anyway, I was surprised after seeing them in the shortlist that neither got selected for the contest... :

kevinatcausa wrote: I'm not sure if I understand this part of your argument: Okay, so I have a sequence that doesn't reach $ M - \{m\}$. But when I change one of the middle hops to be of length $ a_n$, why should I expect the sequence to keep that property? No, you change the second last hop to $ a_n$, thus increasing it (not touching $ m$ but a greater number). The hops until that don't change, and since $ m$ is the greatest of $ M$, it doesn't touch any number in $ M$.

kdano wrote: I was just about to type my solution that's basically the same, and i couldn't find a bug in it either. that is really weird, I've done essentially the same stuff, but can not find any mistake in it either...

probability1.01 wrote: lol... looks like #3 and #6 are of similar flavor this year... For this problem, can't you just

I also tried induction,but I havent finished it yet.

pbornsztein wrote: huang wrote: Did they really consider this hard enough for a problem 6?? As the coordinations take place, it turns to be the most difficult problem of the IMO for the last 50 years in terms of full solutions (maybe only 2, surely less than 5), and in terms of nonzero scores (probably less than 10 contestants will receive a nonzero score). So, please stop with all these complaining about the level of difficulties of the IMO problems (each problem and each year), it becomes ridiculous. Pierre. Sir, who were the two solved this problem? Could you please also check on the sketch posted by probability 1.01.

pbornsztein wrote: huang wrote: Did they really consider this hard enough for a problem 6?? As the coordinations take place, it turns to be the most difficult problem of the IMO for the last 50 years in terms of full solutions (maybe only 2, surely less than 5), and in terms of nonzero scores (probably less than 10 contestants will receive a nonzero score). So, please stop with all these complaining about the level of difficulties of the IMO problems (each problem and each year), it becomes ridiculous. Pierre. Well the idea of induction with carefully chosen numbers was really hard, but I wanted to pointed out that the problem was not hard in technique of solving the problem.

That means absolutely nothing. 2007/3 certainly didn't require anything fancy.

Bugi wrote: Well the idea of induction with carefully chosen numbers was really hard, but I wanted to pointed out that the problem was not hard in technique of solving the problem. I might be overtrained in combinatorics, but I disagree with you. Induction was my second idea for this problem (after some Menger-related stuff, of which i had no knowledge last year, when i was in highschool). Of course one has to work with it to induct appropriately, but one gets promising results while trying to do so. I always wondered how hard people find combinatorics problems.. like i found 2008/5 to be the easiest of all 2008's questions, and what i did for 2007/3 seemed pretty straightforward to me (so straightforward, that i didn't notice that the only cases left don't exist )..

@MellowMelon: But for contestants not manipulating ''advance'' skills, it can be solved with an idea, not just hours and hours of trying to do it, ending up seeing that a solution was something they never seen. Of course, contestants can't know what solves the problem immediately... @kdano: Look at pbornsztein's post. If less than 10 contestants (probably!) would get a non-zero, then how would you call this problem? But, the opinion of the problem is different from man to man, and I agree with you that someone ''overtrained'' could do this more easy.

hello everymathlinkers! I was try this problem and well I think that I've a "solution", I say "solution" because I didnt finish. If : $ X = \{ a_1,...,a_{n + 1} \}$ and $ S_i = \{ a_i +$ $ \displaystyle\sum_{j \in I} a_j$ $ : I \subseteq X - a_i$, when $ I$ diferent to $ X - a_i \}$ for all $ 1\le i \le n + 1$. *** $ A = (a_1,...,a_{n + 1})$ the question is : If $ \exists C_j \in \{0,1\}^{n + 1}$ with $ 1\le i \le n + 1$ and $ d \in Z^ +$ such that $ d = < A,C_j >$ and $ 1 = < C_j,e_j >$ for all $ 1\le i \le n + 1$ and when $ C_j$ cant have all its components equals ??..(*) *** I think that the answer is NO, and if that is true, I can finish my prove, well the idea is induction, then in the step $ n$ to $ n + 1$ I do the next. We know that there exist $ y \in M$ such that there exist $ S_i$ when $ y$ isn't there ( in $ S_i$) (that's true by (*) ) so , we beging "jump it " first to $ a_i$, so in all the next step we cant find $ \displaystyle\sum_{some j but diferent to i} a_j$ $ + a_i$ equal to $ y$. now, if $ M* = M - \{y \}$, then $ z \in M*$ , if $ z$ isnt in $ S_i$ we've no problem but if $ z$ is in $ S_i$ , maybe we can have problems, well , we just only consider $ M* \subseteq S_i$ , then $ z = a_i + z'$, ${ M' = \{ z - a_i : z \in M*}$ then we have $ n - 1$ numbers in $ M'$ and $ n$ distinct numbers $ X - \{a_i\} = X'$ , by the case of n, exist some order for the elements in $ X'$, and we just add $ a_i$ in the beging ,then the induction is complete. . PD: I'm not sure in (*) .

MellowMelon wrote: That means absolutely nothing. 2007/3 certainly didn't require anything fancy. as my teacher says that problem requires a lot of RAM and in fact it was one of the hardest IMO problems ever been proposed...and 2009/6 is certainly easier - since you got hit by the idea that you can induct the problem gets less challenging - which should not be the case if you are dealing with IMO sixth problem.

I agree with Erken. And look at the solutions of them. Which would you easier understand, for which would you think more like, I could've do it?

WLOG let $a_1 < a_2 < a_3\ldots <a_n$ and let $A = \{a_1, a_2, \ldots a_n\}$, and for all $i \in [1, n-1]$, we have $m_i \in M$ and WLOG $m_1 < m_2 < m_3 \ldots < m_{n-1}$. We prove by induction with the base case of $n = 2$ being trivial. For the inductive step, notice by the Pigeonhole Principle that there exists an integer $i$ such that $s-a_i \not\in M$. We have a few cases. Case 1: $m_{n-1} \le s-a_n$. By the inductive hypothesis on $A \setminus \{a_n\}$ and $M \setminus \{m_{n-1}\}$, there exists some way the grasshopper can jump that avoids all the points in $M \setminus \{m_{n-1}\}$, but with the possibility of it landing on $m_{n-1}$. Notice that if it does, we can replace the jump that lands the grasshopper on $m_{n-1}$ with a jump of $a_n$, which successfully brings the grasshopper to a point $p > m_{n-1}$ and have it avoid all points in $M$. Case 2: $m_{n-1} > s-a_n$. If there exists a positive integer $i$ such that $s-a_i \not\in M$ and $s-a_i < m_{n-1}$, then we let $k$ be the index such that $m_k < s-a_i \le m_{k+1}$. We can just apply the inductive hypothesis to $A \setminus \{a_i\}$ and $M \setminus m_k$, and then let the grasshopper jump $a_i$ to reach $s$ where it never touches a point in $M$. Therefore, assume otherwise. We know there must exist an $i$ such that $s-a_i \not\in M$, and let this be maximal. We must have $N = \{s-a_{i+1}, s-a_{i+2}, \ldots s-a_n\} \subseteq M$, where $\#(N) \ge 2$. Therefore, because there must exist some $s-a_n-a_j \not\in M$ for $1 \le j \le i$ by the Pigeonhole Principle, we can use our inductive hypothesis on $A \setminus \{a_j, a_n\}$ and $M \setminus N$ to get the grasshopper to a point $p$ where $p < s-a_n$ and $p+a_n>s-a_{i+1}$, which we then can make it jump $a_n$ and then $a_j$ to reach $s$ without touching a point in $M$. Therefore, the inductive step is proven and we are done. $\blacksquare$ Remarks: I agree with people above that this problem has an easy solution (as I can do it lol), yet is one of the hardest IMO problems to date. Right after reading I instantly thought about induction and because I have unlimited time, I just tried it until I figured out that it worked. However this is a luxury that test-takers do not have and also with it being an "intimidating IMO #6" is probably the reason of its incredibly low solve rate.

I am confused here, does all elements of M are less than S?

Bump, someone please help

abvk1718 wrote: I am confused here, does all elements of M are less than S? You can assume this if it helps your proof because clearly if an element is greater than $s$ then the grasshopper won't be able to jump on it.

jeteagle wrote: abvk1718 wrote: I am confused here, does all elements of M are less than S? You can assume this if it helps your proof because clearly if an element is greater than $s$ then the grasshopper won't be able to jump on it. Got it

We use the method of mathematical induction. Let our jump sizes be $a_1, a_2, \dots a_n$ and the forbidden points be $p_1, p_2, \dots, p_{n - 1}$. Assume $a_1 < a_2 < \dots a_n$ and $p_1 < p_2 \dots < p_n$. There are several cases: Case 1: $a_1 + a_2 + \dots + a_{n - 1} < p_{n - 1}.$ In this case, we can find some permutation of $a_{1}, a_2, \dots a_{n -1}$ which avoids $p_1, p_2, \dots p_{n - 2}$. It would also by default avoid $p_{n - 1}$, by our case 1 assumption. Then, we can jump $a_{n}$ to finish. Case 2: $a_1 + a_2 + \dots + a_{n - 1} \ge p_{n - 1}.$ In this case, let's also use some permutation of $a_1, a_2, \dots a_{n - 1}$ that avoids $p_1, p_2, \dots p_{n - 2}$. If that ordering also avoids $p_{n -1 }$, we're done, so let's assume that it hits $p_{n - 1}$ at some point. At the point where it hits $p_{n - 1}$, swap $a_i$ with $a_n$. Then, the path will be valid.

in the official booklet. Personally, I was also looking at least $k$ for which $|M \cap (0,T_k]| \ge k$ (as that's sort of a generalization to the case when $M$ contains an element $\le a_1$, which is easy to resolve by induction). But I was unable to finish from there.

We induct on $n$, with the base case $n=1$ obvious. Set $a_1 < a_2 < \cdots < a_n$. For the inductive step, we split into four cases: Case 1. $s-a_n \in M$ is the maximal element of $M$. In this case, by the inductive hypothesis, there exists a sequence of jumps with lengths $a_1, a_2, \cdots, a_{n-1}$ that can avoid the first $n-2$ elements of $M$. Let $a_k$ be the last jump in this sequence. Then, instead of jumping $a_k$ and then $a_n$, we can jump $a_n$ and then $a_k$, which avoids the last mine, so we are done. Case 2. $s-a_n \in M$, and there are elements of $M$ greater than $s-a_n$. First, notice that of the $n-1$ values $s-a_k$, $1 \leq k \leq n-1$, one of them must not be in $M$ because $M$ has at most $n-2$ elements in this range. Now, suppose there are $k$ elements of $M$ after $s-a_n$. Then, there are at least $n-k-1$ values $i$ such that $s-a_{n-1-i}$ is not in $M$. Because there are at most $n-k-2$ elements in $M$ before $s-a_n$, there must exist an index $i$ such that $s-a_{n-1-i} - a_n$ is not in $M$. Now, there are at most $n-3$ elements of $M$ left and we have $n-2$ jumps remaining, so it is possible to avoid all these points via a sequence of jumps. Case 3. $s-a_n \not \in M$, and there are elements of $M$ greater than $s-a_n$. This case is obvious; simply make a mine-avoiding sequence of jumps to $s-a_n$, then jump $a_n$. Case 4. $s-a_n \not \in M$, and all elements of $M$ are strictly less than $s-a_n$. Let $m$ be the maximal element of $M$. There exists a sequence of jumps in $\{a_1, a_2, \cdots, a_{n-1}\}$ that avoids all elements of $M$ except for $m$. If it avoids $m$ as well, it lands on $s-a_n$, and we are done. If it lands on $m$, then on the jump right before it reaches $m$, change the grasshopper's jump length to $a_n$, which guarantees that it lands on a safe square as $m$ is maximal. Next, make the remaining jumps to reach $s$, as needed. Thus, the induction is complete, and we are done.

Define $m=\max M,$ $A=\left \{ a_1,a_2, \dots ,a_n\right \}$ and WLOG $a_n=\max a_i$. We induct on $n;$ base case $n\in \left \{ 1,2\right \}$ is trivial. For $n>2$ consider two cases. Case 1. $s-a_n\geq m.$ By inductive hypothesis there exist a sequence of jumps by lengths $A\backslash a_n$ which avoid points from $M\backslash m$ - add a jump by $a_n$ at the end. If the jump by $a_i$ leads to point $m,$ we swaps order of jumps by $a_i,a_n$ - clearly this works. Case 2. $s-a_n<m.$ If $(s-a_n)\notin M'=M\backslash m,$ construct by hypothesis a sequence of jumps by $A\backslash a_n$ which avoid points from $M',$ adding $a_n$ at the end. Otherwise, by PHP there exist pair of numbers $(s-a_k,s-a_n-a_k)$ not belonging to $M'$ - construct a sequence of jumps by $A\backslash a_k \backslash a_n$ avoiding points of $M'\backslash a_k,$ and adding consequent jumps by $a_n,a_k$ at the end, which works.

Can someone confirm that this is correct? I'm not sure but the problem statement seemed really clear and easy... We use induction. Let our jump sizes be $a_1<a_2<\dots<a_n$ and the forbidden points be $f_1<f_2<\dots<f_{n - 1}$. The base case n=1 and n=2 are obvious. If $a_1 + a_2 + \dots + a_{n - 1} < p_{n - 1}$, by inductive hypothesis use some ordering of $a_{1}, a_2, \dots a_{n -1}$ which avoids $p_1, p_2, \dots p_{n - 2}$. Then, we can jump $a_{n}$ to finish. If $a_1 + a_2 + \dots + a_{n - 1} \ge p_{n - 1}$, use inductive hypothesis again on some ordering of $a_1, a_2, \dots a_{n - 1}$ that avoids $p_1, p_2, \dots p_{n - 2}$; if it also avoids $p_{n -1 }$, we're done, but if it hits $p_{n - 1}$ after jumping $a_k$, we know that $p_{n-1}>p_{n-2},...,p_1$ implies that jumping $a_k$ jumps past the points; in particular, we can move $a_n$ instead of $a_k$ at that move, since it will jump a further distance past all points.

solved with hints Induct on $n$. This is clearly true for $n=1,2$. Define a critical point as a point that is the sum of $n-1$ out of the $a_i$. Define a trap as an element of $M$. Consider the smallest critical point, $c$. If there is no trap on $c$ and no trap after $c$, then there are $n$ traps between 0 and $c$. Ignore the last trap before $c$ for now, by induction we can then find a path to $c$ since there are only $n-2$ traps ignoring that one and then we could finish and jump from $c$ to $s$. The only issue is that we might hit the last trap. However, if we do, make the largest possible move in place of the move that stepped on the last trap, which would guarantee skipping it as the largest move is not part of the road to $c$ as $c$ does not contain that term. If there is no trap on $c$ and trap after $c$, we can directly induct to find a path to $c$, as there are at most $n-2$ traps in that area, so we would be done. If there is a trap on $c$ but it is the furthest one along and there are no traps after $c$, take a path that would get you to $c$ except replace the last move with the largest possible move and then finish with whatever move is left. Finally, if there is a trap on $c$ and also a trap past $c$, consider the points that is one "jump" away from $c$, and the corresponding point that is that same jump away from $s$. There are $n-1$ such pairs, but with only $n-2$ traps other than the one at $c$, there must be a pair of these points that are both safe. Since there are at most $n-3$ traps before $c$, we can reach the point that is one jump away from $c$. Then, the last two jumps are used to get the corresponding point by making the largest jump and then finally jumping to the end.

Let's prove this statement by induction on $n$, the number of jumps the grasshopper makes. Base case: When $n = 2$, there is only one jump with length $a_1$ or $a_2$. Since $M$ contains $n - 1 = 1$ integer and cannot contain $s = a_1 + a_2$, the grasshopper can simply make the jump to the right with the remaining length and avoid landing on the point in $M$. Inductive step: Assume the statement holds for $n = k$, where $k$ is some positive integer. We'll prove it for $n = k + 1$. Let the sequence of positive integers be $a_1, a_2, \ldots, a_{k+1}$, and let $M$ be a set of $k$ positive integers not containing $s = a_1 + a_2 + \ldots + a_{k+1}$. Consider $M'$, which is obtained by adding $s$ to each element of $M$, i.e., $M' = {m + s \mid m \in M}$. By the induction hypothesis, there exists an order in which the grasshopper can jump $k$ times among $a_1, a_2, \ldots, a_k$ without landing on any point in $M$. Let $p$ be the position after these $k$ jumps. Now, if $p + a_{k+1} \notin M'$, the grasshopper can make the $k+1$-th jump to the right with length $a_{k+1}$ and avoid landing on any point in $M$ since $p + a_{k+1}$ cannot be in $M'$. If $p + a_{k+1} \in M'$, then $p + a_{k+1} = m + s$ for some $m \in M$. But $p + a_{k+1} - s = p - (a_1 + a_2 + \ldots + a_k) = p - s$, which means $p - s = m \in M$. However, $p - s$ is the position after $k$ jumps, which, by the induction hypothesis, does not land on any point in $M$. This contradicts $p - s = m \in M$. Therefore, $p + a_{k+1} \notin M'$, and the grasshopper can make the $(k+1)$-th jump without landing on any point in $M$. By induction, the statement holds for all positive integers $n$.

Proceed by induction on $n$. Let $a_1<a_2<\dots<a_n$. Then, suppose $\max{M}>s-a_n$ and $s-a_n\not\in M$. Then, by the induction hypothesis, there exists a path from $0$ to $s-a_n$ that avoids all integers in $M$ that uses jumps $a_1$, $a_2$, $\dots$, $a_{n-1}$. Then, once at $s-a_n$, the grasshopper can jump $a_n$ and win. If $\max{M}\le s-a_n$ then consider the path that the grasshopper would take if we removed $\max{M}$ from $M$. If it doesn't hit $\max{M}$, we're all good. If it does, then replace that move with a larger one. We can always do this since $a_n$ is available. The remaining case is $\max{M}>s-a_n$ and $s-a_n\in M$. Let $S'=\{\{s-a_n-a_i, s-a_i\}\mid 1\le i\le n-1\}$. Note that $|S'|=n-1$ and $|M\setminus \{s-a_n\}|=n-2$, there exists an element $k\in S'$ such that $|M\cap k|=0$. Note that $|M\cap \{1,2,\dots,s-a_n-a_i-1\}|\le n-3$, so by the induction hypothesis, the grasshopper can jump to $s-a_n-a_i$ and then to $s-a_i$ and then to $s$.

Groupsolved with cursed_tangent1434. We will use induction, and WLOG $a_1 < a_2 < a_3 < \ldots < a_n$, and let the elements of set $M$ be $m_1 \leq m_2 \leq m_3 \leq \ldots \leq m_{n-1}$. $\newline$ Our base case of $n = 1$ is clearly true, and so is our $n = 2$ case. $\newline$ Now assume that $n - 1$ works. We then have to prove that for any choice of $m_{n-1}$ and choice of $a_n$ then it is possible to order the jumps in a way so that we land on $a_1 + a_2 + \ldots + a_n = s$ without touching an element of $M$. $\newline$ Case $1$: $s - a_n < m_{n-1}$ From here, we can simply add $a_n$ to $s - a_n$ to reach $s$. Note that it is possible to reach $s - a_n = a_1 + a_2 + \ldots + a_{n-1}$ since our $n - 1$ case is true. $\newline$ Case $2$: $s - a_n \geq m_{n-1}$ If $m_{n-1}$ does not coincide with the points the grasshopper jumps on, then we're done by simply adding $a_n$ to $s - a_n$. If otherwise, then swap the distance that the grasshopper jumped to land on $m_{n-1}$ with $a_n$. Since $m_{n-1}$ is the maximum value in $M$ and that $a_n \geq m_{n-1}$, this avoids all other elements of $M$, and leads the grasshopper to $s$. So, our induction is done. $\blacksquare$

We proceed with induction. The base cases $n=1,2$ are trivial. Now assume that the proposition holds for all $n \leq k$ for some positive integer $k \geq 2.$ Then we will prove the proposition for $n=k+1:$ Suppose that we have the $k+1$ numbers $a_1 < a_2 < \cdots < a_{k+1}$ and the $k$ forbidden positions $x_1 < x_2 < \cdots < x_k$ which form $M.$ Let $d=s-a_{k+1}.$ We consider cases. $\textbf{Case 1: }$ If $d < x_k,$ and $d \notin M,$ then clearly we can get to $d$ by the inductive hypothesis for $n=k$ by avoiding all the forbidden positions $x_1, x_2, \dots, x_{k-1},$ and then get to $s.$ $\textbf{Case 2: }$ Now, suppose that $d < x_k$ and $d \in M.$ Let there be $m$ forbidden points beyond $d$ (not including it). Then there are $k-m-1$ forbidden points less than $d.$ Note that we can apply the inductive hypothesis for $n=k-1$ to get to $d-a_j$ for some $1 \leq j \leq k,$ and then going to $s-a_j.$ Clearly there are $k-(k-m-1)=m+1$ possible values for $j$ that avoid $x_1, x_2, \dots, x_{k-m-1}, x_{k-m}=d.$ Then, there are $m+1$ possible values for $s-a_j.$ Clearly, at least one of them is not going to be equal to an $x_i$ because there are only $m$ $x_i$s greater than $d.$ Therefore, from this point we can get to $s.$ $\textbf{Case 3: }$ Meanwhile, consider if $d > x_k.$ Then clearly $d \notin M.$ By the inductive hypothesis for $n=k,$ we can get to $d$ while avoiding $x_1, x_2, \dots, x_{k-1}.$ Then, we can use $a_k$ to get to $s.$ However, if at any point we reached $x_k$ with the move $a_j,$ swap $a_j$ with $a_k,$ and this will yield a valid construction. This is because $a_k > a_j,$ so we would pass $x_k,$ and therefore also $x_1, x_2, \dots, x_{k-1}.$ Then, we can do whatever sequence of moves that we have left without hitting these forbidden positions, ending at $s.$ Therefore, all cases have been proven so our induction is complete. QED