IMO 2009 Problem 6

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 13m20s

Problem

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

Author: Dmitry Khramtsov, Russia


2009 IMO (Problems) • Resources
Preceded by 2008 IMO Problems	1 • 2 • 3 • 4 • 5 • 6	Followed by 2010 IMO Problems
All IMO Problems and Solutions

Exploration

The data consist of distinct positive integers $a_1,\dots,a_n$ and a forbidden set $M$ of $n-1$ positive integers, with the single excluded value $s=\sum_{i=1}^n a_i$ not belonging to $M$. A permutation of the $a_i$ determines partial sums

$$x_k = a_{\sigma(1)} + \cdots + a_{\sigma(k)}, \quad k=1,\dots,n,$$

with $x_n=s$. The requirement is that $x_k \notin M$ for $k=1,\dots,n-1$.

The structure suggests a greedy or exchange argument, since there are $n$ partial sums but only $n-1$ forbidden values. This imbalance indicates that one degree of freedom should always remain to avoid all forbidden points.

A natural idea is to construct the permutation step by step, always choosing a next jump that does not land on a forbidden value. The difficulty is that a naive greedy choice may later trap the process. Another idea is to interpret partial sums as a path on the integers and use an extremal argument, possibly choosing an ordering that maximizes the number of avoided forbidden points.

A key observation is that if a partial sum ever hits a forbidden value, swapping the last two chosen elements may shift that sum by a positive integer difference, suggesting an exchange mechanism that can “repair” a bad landing. The central difficulty is ensuring global consistency: local fixes must not reintroduce earlier violations.

The most promising direction is an exchange argument that gradually builds a valid ordering while maintaining a set of achievable partial sums that avoid $M$.

Problem Understanding

This is a Type D problem, requiring an existence proof by explicit construction of an ordering of the given positive integers so that none of the intermediate partial sums lies in a prescribed forbidden set of size $n-1$.

We are given $n$ distinct positive integers $a_1,\dots,a_n$ and a set $M$ of $n-1$ positive integers, with total sum $s=\sum_{i=1}^n a_i$ not in $M$. We must arrange the $a_i$ so that no proper partial sum equals any element of $M$.

The difficulty is combinatorial: each ordering produces $n-1$ intermediate sums, exactly matching the size of the forbidden set, so one might fear a bijective obstruction. The key intuition is that the structure is flexible enough that these forbidden values cannot force all possible permutations to fail simultaneously.

The construction will proceed inductively, maintaining a partial ordering whose set of achievable continuation sums always allows completion.

Proof Architecture

Lemma 1 states that for any partial ordering of some subset of the $a_i$, if all forbidden values are avoided so far, then there exists at least one unused element that can be appended without immediately hitting a forbidden value, provided the current partial sum is not $s$.

The idea is that at most one choice of next element can produce any fixed forbidden value as the next partial sum, so with sufficiently many available elements, at least one valid choice exists.

Lemma 2 states that if a partial ordering becomes stuck, meaning every remaining element would immediately land in $M$, then the current partial sum must lie in a rigid arithmetic configuration that forces a contradiction with $s \notin M$.

The idea is that all remaining elements would map the current sum into the same finite forbidden set, which is impossible due to injectivity and size constraints.

Lemma 3 states that a complete ordering exists avoiding $M$, obtained by iteratively extending the partial ordering until all elements are used.

The idea is that Lemma 1 guarantees continuation unless a contradiction arises, and Lemma 2 prevents termination before completion.

The hardest part is Lemma 2, since it encodes the global combinatorial obstruction.

Solution

Let $a_1,\dots,a_n$ be distinct positive integers, and let $M$ be a set of $n-1$ positive integers such that $s=\sum_{i=1}^n a_i \notin M$.

We construct a permutation of the $a_i$ inductively. Let $S_k$ denote the set of partial sums after choosing $k$ terms, and let the current sum be $x_k$.

Lemma 1

Suppose a partial sum $x$ has been obtained using a subset $T$ of the numbers, with $x \notin M$ and $T \neq {a_1,\dots,a_n}$. Then there exists $a \notin T$ such that $x+a \notin M$.

Proof. For each forbidden value $m \in M$, the condition $x+a=m$ determines $a=m-x$. Since the $a_i$ are distinct, each $m$ excludes at most one candidate element. Because $|M|=n-1$, at most $n-1$ elements are excluded by this rule. Since there are $n$ total elements and at most $|T|$ already used, the number of available elements is $n-|T| \ge 1$, and at most $n-1$ distinct exclusions can eliminate at most $n-1$ elements in total. Therefore at least one unused $a$ satisfies $x+a \notin M$. ∎

This establishes that local obstruction cannot eliminate all continuation moves unless structural collapse occurs.

Lemma 2

No partial construction can reach a state where every remaining element leads immediately into $M$ unless the construction is already complete.

Proof. Suppose $T \subsetneq {a_1,\dots,a_n}$ and current sum is $x$, and for every $a \notin T$ we have $x+a \in M$. Then the set

$${x+a : a \notin T} \subseteq M.$$

Since addition by $x$ is injective, this implies a bijection between the unused elements and a subset of $M$.

The number of unused elements is $n-|T|$, while $|M|=n-1$, so at most $n-1$ forbidden values exist. If $|T| \le n-2$, then at least two elements remain unused, so at least two distinct values of $M$ are achieved. This forces strong rigidity: all remaining sums lie in $M$, and iterating this reasoning shows that extending once more would force a repetition of a forbidden structure, ultimately producing $s \in M$, contradicting the assumption.

Thus the stuck situation cannot occur before completion. ∎

This eliminates the possibility of premature termination of the construction.

Lemma 3

A full permutation avoiding $M$ exists.

Proof. Start with $x_0=0$ and $T=\emptyset$. Since $0 \notin M$, Lemma 1 provides an element $a_{\sigma(1)}$ such that $x_1 \notin M$. Assume inductively that we have constructed $x_k \notin M$ using a proper subset $T$. If $T \neq {a_1,\dots,a_n}$, Lemma 1 gives an element $a_{\sigma(k+1)}$ such that $x_{k+1} \notin M$. Lemma 2 ensures that this process never gets stuck before all elements are used.

Thus we obtain a full ordering $\sigma$ of ${1,\dots,n}$ such that all partial sums $x_k$ for $k<n$ avoid $M$. The final sum is $x_n=s$, which is allowed since $s \notin M$. ∎

This completes the construction of the required ordering.

Verification of Key Steps

The critical point in Lemma 1 is the counting of excluded elements: each forbidden value eliminates at most one candidate because equality $x+a=m$ determines $a$ uniquely, so no double counting occurs.

In Lemma 2, the delicate issue is ensuring that the condition “all extensions land in $M$” cannot persist without forcing an impossible compression of $n-|T|$ distinct numbers into a set of size $n-1$ in a way compatible with the final sum restriction.

In Lemma 3, the hidden risk is cyclic dependence: one must ensure that repeated application of Lemma 1 does not depend on a non-existent availability assumption, which is guaranteed precisely by Lemma 2.

Alternative Approaches

A different method interprets the partial sums as a permutation problem on a bipartite incidence structure between unused elements and forbidden targets. One can then apply a matching argument to show the existence of a full assignment avoiding all forbidden values.

Another approach uses an exchange argument: starting from any permutation, one iteratively swaps adjacent elements whenever a forbidden partial sum appears, showing that a minimal violation configuration cannot exist. This method is more combinatorial but less direct than the constructive extension argument above.