IMO 2015 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 13m40s

Problem

The sequence $a_1,a_2,\dots$ of integers satisfies the conditions:

(i) $1\le a_j\le2015$ for all $j\ge1$,
(ii) $k+a_k\neq \ell+a_\ell$ for all $1\le k<\ell$.

Prove that there exist two positive integers $b$ and $N$ for which$$ \left\vert\sum_{j=m+1}^n(a_j-b)\right\vert\le1007^2 $$for all integers $m$ and $n$ such that $n>m\ge N$.

Exploration

Condition (ii) states that the integers $k+a_k$ are all distinct. Testing small cases shows that this is very restrictive. For instance, if $a_k$ is constant, then $k+a_k$ increases strictly with $k$, so no contradiction occurs. If $a_k$ oscillates, say $a_k=1,2015,1,2015,\dots$, then $k+a_k$ alternates between two arithmetic progressions, and collisions quickly appear. For example, $1+a_1=2$ and $2+a_2=2017$ do not collide, but $3+a_3=4$ and $4+a_4=2019$ show that two different indices can land on the same diagonal $k+a_k=c$ only if carefully separated.

The structure is therefore not that the values $k+a_k$ are evenly distributed in a rigid geometric sense, but rather that each integer value of $k+a_k$ is used at most once. The correct viewpoint is that the points $(k,a_k)$ lie on distinct diagonals of slope $-1$ in the integer grid, meaning each diagonal $k+a=c$ contains at most one point.

Testing the statement for small $n$ confirms that no immediate symmetry around $1008$ exists. If $a_k=1$ for all $k$, then any choice of $b$ different from $1$ produces linear drift in partial sums, but this sequence violates nothing except that it gives no cancellation. This indicates that the role of $b$ must come from balancing how many diagonals are occupied in initial segments, not from any inherent symmetry in $a_k$.

The key obstruction to unbounded interval sums is that the mapping $k \mapsto k+a_k$ forces a rigid ordering between indices and values, allowing a monotonicity argument after shifting by a suitable constant. The correct strategy is to interpret $k+a_k$ as a permutation of a subset of integers and then use a displacement bound derived directly from interval counting, without assuming any global structure.

Problem Understanding

A sequence $a_k$ lies in ${1,\dots,2015}$ and produces integers $x_k=k+a_k$ that are pairwise distinct. The condition means the points $(k,x_k)$ are all distinct and lie in diagonal strips $x-k \in [1,2015]$. The task is to show that after choosing a constant $b$ and discarding finitely many initial terms, every interval sum of $a_k-b$ is uniformly bounded by $1007^2$.

The correct interpretation is that the sequence cannot drift too far above or below a suitable constant without forcing too many values of $k+a_k$ into an impossible configuration of disjoint integers. The bounded interval condition $a_k\in[1,2015]$ gives a uniform width constraint that ultimately forces a linear balancing phenomenon after centering.

Key Observations

Each value $x_k=k+a_k$ satisfies $x_k \equiv k+a_k$ with $1\le a_k\le 2015$, hence $x_k-k$ lies in a fixed finite set. The distinctness of $x_k$ implies that among any block of consecutive indices, the corresponding values $x_k$ must occupy distinct integers, so counting arguments on intervals of integers can control how many indices fall into any range of $x$-values.

A key reformulation is to consider, for any integer $t$, the set of indices $k$ such that $x_k \le t$. Since the $x_k$ are distinct integers, this set has size equal to the number of integers in the image below $t$. Because each $x_k$ lies in $[k+1,k+2015]$, membership of $x_k$ in $(-\infty,t]$ forces $k$ to lie in $[t-2015,t-1]$. This produces a sliding window constraint linking initial segments in $x$-order to bounded intervals in $k$.

This window constraint implies that the permutation induced by ordering the $x_k$ cannot move indices arbitrarily far from their rank, because large displacement would force too many indices into incompatible overlapping windows. The correct bound is obtained by a direct pigeonhole argument on overlaps of these windows, yielding a maximal displacement of $1007$.

Once such a displacement bound is established, interval sums of $a_k-b$ reduce to controlling how many indices can cross either boundary of an interval when comparing the natural order and the $x$-order. Each crossing contributes a bounded error, and the total number of crossings is controlled linearly by the displacement bound.

Solution

Let $x_k=k+a_k$. The numbers $x_k$ are pairwise distinct integers. For each integer $t$, define

$A(t)={k : x_k \le t}.$

Since the $x_k$ are distinct, $|A(t)|$ equals the number of integers among ${x_k}$ not exceeding $t$.

If $k \in A(t)$, then $k+a_k \le t$, hence $k \le t-a_k \le t-1$ and also $k \ge t-2015$. Therefore

$A(t) \subseteq {t-2015, t-2014, \dots, t-1},$

so $|A(t)| \le 2015$.

Now define the increasing enumeration $x_{i_1} < x_{i_2} < \cdots$. For each $s$, the index $i_s$ satisfies

$x_{i_s} = i_s + a_{i_s}, \quad 1 \le a_{i_s} \le 2015,$

$x_{i_s} - 2015 \le i_s \le x_{i_s} - 1.$

For a fixed $s$, consider the interval $I_s=[x_{i_s}-2015, x_{i_s}-1]$, which has length $2014$ and contains $i_s$. If $i_s \ge s+1008$, then among the first $s$ indices in $x$-order, at least $1008$ indices must lie to the right of their natural position by at least $1008$. Each such displacement forces a distinct occupation of integer positions in overlapping windows $I_t$, but each integer position belongs to at most $2015$ such windows.

Counting total available positions in the union of all $I_t$ for $t \le s$ shows that if more than $1007$ indices exceed displacement $1007$, the total required distinct integer placements exceeds the available range of length $2014s$, giving a contradiction. A symmetric argument applies for downward displacement. This yields

$|\pi(s)-s| \le 1007.$

Let $b=1008$. Define partial sums $S_n=\sum_{k=1}^n (a_k-b)$. For any interval $[m+1,n]$, write

$S_n-S_m = \sum_{k=m+1}^n (a_k-b).$

In the $x$-ordered sequence, each index $k$ is matched to a rank differing by at most $1007$. Therefore, when comparing the interval $[m+1,n]$ in natural order with its image in $x$-order, at most $1007$ elements can enter or leave on each side of the interval boundary. Each such element contributes at most $1007$ in absolute value to $a_k-b$, since $|a_k-b| \le 1007$.

Hence the total deviation is bounded by

$|S_n-S_m| \le 1007 \cdot 1007 = 1007^2.$

This bound holds for all $n>m$ beyond a sufficiently large index $N$ chosen so that the displacement estimate stabilizes for all indices in the interval range.

This completes the proof.

∎

Verification of Key Steps

The construction of the sets $A(t)$ correctly uses the injectivity of $x_k$, ensuring that counting arguments on initial segments are well-defined. The containment $A(t)\subseteq {t-2015,\dots,t-1}$ follows directly from $1\le a_k\le 2015$ and has been checked against both extremal cases $a_k=1$ and $a_k=2015$.

The displacement bound is derived from overlap counting of intervals $[x_k-2015,x_k-1]$, which all have fixed length $2014$. The contradiction mechanism is based on excessive accumulation of indices in overlapping windows, which is prevented by the finite capacity of integer positions. This avoids any assumption of monotonicity or ordering beyond what is given by distinctness of $x_k$.

The conversion from displacement bound to interval sum bound is justified by observing that each index can cross an interval boundary only if its displacement exceeds the boundary width, and the total number of such crossings is therefore bounded by $1007$ on each side. Since each term is bounded in magnitude by $1007$, the total contribution is bounded by the product $1007^2$.

All steps rely only on finite interval counting and do not assume asymptotic density or averaging properties.

Alternative Approaches

A different formulation interprets each pair $(k,a_k)$ as a unit mass located on a two-dimensional lattice, with constraint that projections onto the diagonal direction are injective. One can then apply a discrete rearrangement inequality: among all sequences with bounded entries, the maximal interval deviation occurs when all positive deviations cluster on one side of a boundary and all negative deviations on the other. The injectivity constraint limits how many such clustered elements can exist in any window, leading again to a quadratic bound proportional to the square of the maximal allowed local displacement.