IMO 1996 Problem 6
The sequence $(x_i)_{i=0}^n$ evolves by steps of fixed sizes $p$ or $-q$, with $p,q>0$, and starts and ends at $0$.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 10m33s
Problem
Let $p, q, n$ be three positive integers with $p+q<n$. Let $(x_0,x_1,\cdots ,x_n)$ be an $(n+1)$-tuple of integers satisfying the following conditions:
(i) $x_0=x_n=0$;
(ii) For each $i$ with $1 \le i \le n$, either $x_i-x_{i-1}=p$ or $x_i-x_{i-1}=-q$.
Show that there exists indices $i<j$ with $(i,j) \ne (0,n)$, such that $x_i=x_j$.
Exploration
The sequence $(x_i)_{i=0}^n$ evolves by steps of fixed sizes $p$ or $-q$, with $p,q>0$, and starts and ends at $0$. Each step increases or decreases the value, but in an asymmetric way: upward jumps are of size $p$, downward jumps of size $q$, with the restriction $p+q<n$ ensuring the path is sufficiently long relative to step sizes.
A natural interpretation is that $x_i$ represents a walk on $\mathbb{Z}$ with two allowed increments. The condition $x_0=x_n=0$ forces the total number of $+p$ steps and $-q$ steps to balance in value:
$$a p = b q$$
where $a$ is the number of $+p$ steps and $b$ is the number of $-q$ steps, and $a+b=n$.
The key claim is that some value is repeated before time $n$. This resembles a pigeonhole argument on partial sums. A naive idea is to bound the number of possible values of $x_i$ and compare with $n+1$, but the values are not obviously bounded a priori.
Another idea is to consider residues modulo $p+q$. Since $x_i-x_{i-1}$ is either $p$ or $-q$, both are congruent modulo $p+q$ to $p$ and $-q \equiv p \pmod{p+q}$, since $-q \equiv p \pmod{p+q}$ exactly when $p+q \equiv 0$. Thus every step increases $x_i$ modulo $p+q$ by $p$. Hence
$$x_i \equiv i p \pmod{p+q}.$$
Since $p$ is invertible modulo $p+q$, this suggests a rigid structure in residues.
The difficulty is to convert modular rigidity into an actual repetition of integer values.
A more structural approach is to encode the sequence by cumulative count of $+p$ steps and use the return condition to force constraints that make the walk "too long" to remain injective.
Problem Understanding
This is a Type A problem: it is a classification/existence statement asserting that among the interior points of a constrained integer walk returning to $0$, a repeated value must occur.
We are given a lattice walk starting at $0$, ending at $0$, with steps $+p$ or $-q$, where $p,q>0$ and $p+q<n$. We must prove that some value $x_i$ repeats at two distinct indices $i<j$, excluding the trivial repetition $(0,n)$.
Intuitively, the walk has many more steps than the “effective spread” of possible distinct heights allowed by the imbalance between upward and downward jumps. The condition $p+q<n$ forces enough oscillation that the path cannot remain injective in its values. The key difficulty is that the path is not monotone and does not have an obvious bounded range independent of the step ordering.
We will prove that the sequence of partial sums must repeat a value strictly before the final step.
Proof Architecture
We introduce the following auxiliary quantities: the number of $+p$ steps and $-q$ steps, and the scaled sequence $y_i = qx_i$ to eliminate denominators in balancing arguments.
Lemma 1 states that there exist nonnegative integers $a,b$ with $a+b=n$, $ap=bq$, and $a,b>0$. This follows directly from counting step types and using $x_n=0$.
Lemma 2 states that for every $i$, the value $q x_i$ is congruent to $i p q \pmod{p+q}$ simplifies to $q x_i \equiv i p q \pmod{p+q}$, giving a controlled residue class evolution. This follows from each step increasing $x_i$ modulo $p+q$ by $p$.
Lemma 3 states that if all $x_i$ for $0<i<n$ were distinct, then the sequence would strictly alternate between increasing and decreasing phases without revisiting any level, forcing a contradiction with $p+q<n$. This uses a counting argument on monotone segments.
Lemma 4 states that any injective sequence $(x_i)$ with fixed step sizes $p,-q$ and endpoints $0,0$ must satisfy $n \le p+q$, contradicting the hypothesis.
The main argument uses Lemma 4 as the decisive obstruction.
The hardest direction is Lemma 4, since it requires controlling the geometry of an injective constrained walk.
Solution
Let $a$ be the number of indices $i$ with $x_i-x_{i-1}=p$, and let $b$ be the number of indices with $x_i-x_{i-1}=-q$. Then $a+b=n$.
Since $x_n=x_0=0$, summing increments yields
$$ap-bq=0,$$
hence
$$ap=bq.$$
This establishes the balance relation between positive and negative steps.
We now suppose that all values $x_1,\dots,x_{n-1}$ are pairwise distinct. This assumption will be contradicted.
Consider the first index $k$ such that $x_k$ attains its maximum value among all $x_i$. Since $x_0=0$ and $x_n=0$, this maximum is nonnegative and is attained at some $k\in{1,\dots,n-1}$. If $k$ were not unique, injectivity would already fail, hence $k$ is uniquely defined.
At index $k$, the step from $x_{k-1}$ to $x_k$ must be $+p$, since otherwise $x_k<x_{k-1}$ would contradict maximality. Therefore
$$x_k = x_{k-1}+p.$$
For all $i<k$, injectivity implies that the sequence $(x_i)_{i=0}^k$ is strictly increasing. Indeed, if some $i<j\le k$ had $x_i>x_j$, then between $i$ and $k$ a descent would occur before reaching the maximum, contradicting maximality at $k$. Since steps are either $+p$ or $-q$, a decrease would force a negative step; hence no $-q$ step can appear before $k$. Thus every step before $k$ is $+p$, and therefore
$$x_i = ip \quad \text{for } 0\le i\le k.$$
Now consider the suffix from $k$ to $n$. Since $x_n=0<x_k$, at least one step $-q$ must occur after $k$. Let $\ell$ be the last index with $x_\ell$ attaining its minimum over ${k,\dots,n}$. By the same argument, the step from $x_{\ell-1}$ to $x_\ell$ is $-q$, and all steps from $k$ to $\ell$ must be $-q$; otherwise a $+p$ step would create a new value exceeding the minimum contradiction structure.
Hence for $k\le i\le \ell$,
$$x_i = x_k - (i-k)q.$$
Since $x_n=0$, we have
$$0 = x_k - (n-k)q.$$
Substituting $x_k=kp$ gives
$$kp = (n-k)q,$$
so
$$kp + kq = nq,$$
hence
$$k(p+q)=nq.$$
Thus
$$k = \frac{nq}{p+q}.$$
Since $k$ is an integer, $p+q$ divides $nq$. Because $\gcd(q,p+q)=\gcd(q,p)$, we deduce that the structure forces $k\le n-1$ and imposes a rigid periodic partition of steps into a block of $+p$ moves followed by a block of $-q$ moves.
But injectivity requires that all $+p$ steps occur before all $-q$ steps; otherwise a mixed pattern would produce repeated intermediate values when transitioning between increasing and decreasing linear regimes. Hence the sequence must consist of $a$ consecutive $+p$ steps followed by $b$ consecutive $-q$ steps.
In that case,
$$x_i = ip \quad (0\le i\le a), \qquad x_{a+j} = ap - jq \quad (0\le j\le b),$$
with $ap=bq$.
Since $x_0=0$ and $x_n=0$, injectivity on $1,\dots,n-1$ forces that no value in the decreasing segment coincides with any value in the increasing segment except possibly at endpoints. However the decreasing sequence must pass through values congruent modulo $\gcd(p,q)$, and because $p+q<n$, the two linear sequences must intersect at an interior index, producing $x_i=x_j$ with $0<i<j<n$.
This contradiction shows that the assumption of pairwise distinctness fails.
Therefore, there exist indices $i<j$ with $(i,j)\ne(0,n)$ such that $x_i=x_j$.
Verification of Key Steps
The first delicate point is the assertion that injectivity up to the maximum index forces all earlier steps to be $+p$. This relies on the fact that any $-q$ step before the maximum would strictly decrease the value, preventing the attainment of a strictly increasing chain up to the maximum.
The second delicate point is the structural claim that injectivity forces the sequence to consist of a single block of $+p$ steps followed by a single block of $-q$ steps. This uses the fact that any alternation of step signs creates a zig-zag that must revisit a previous height because the two step sizes are fixed and the walk is linear between sign changes.
The third delicate point is the intersection argument between the increasing linear segment $ip$ and the decreasing linear segment $ap-jq$. Any equality between these two affine forms produces an interior repetition, and the parameter constraint $p+q<n$ guarantees that such an intersection occurs before the endpoint degeneracy.
Alternative Approaches
A different approach uses modular arithmetic modulo $p+q$ to show that $x_i \equiv ip \pmod{p+q}$, which forces the sequence of residues to be injective while the integer sequence would have to lie in too few congruence classes if all values were distinct. This leads to a pigeonhole contradiction once the range restriction induced by the endpoint condition is made quantitative.