IMO 1996 SL C5

Origin: FRA | Category: Combinatorics

Problem

Let $p, q, n$ be three positive integers with $p + q < n$.

Let $(x_0, x_1, \dots, x_n)$ be an $(n+1)$-tuple of integers satisfying the following conditions:

$x_0 = x_n = 0$.
For each $i$ with $1 \leq i \leq n$, either $x_i - x_{i-1} = p$ or $x_i - x_{i-1} = -q$.

Show that there exists a pair $(i, j)$ of distinct indices with $(i, j) \neq (0, n)$ such that $x_i = x_j$.

Solution

Note that w.l.o.g., we can assume that $p$ and $q$ are coprime. Indeed, otherwise it suffices to consider the problem in which all $x_i$’s and $p, q$ are divided by $\gcd(p, q)$.

Let $k, l$ be the number of indices $i$ with $x_{i+1} - x_i = p$ and the number of those $i$ with $x_{i+1} - x_i = -q$ ($0 \leq i < n$). From $x_0 = x_n = 0$ we get $k p = l q$, so for some integer $t > 1$, $k = q t$, $l = p t$, and $n = (p + q) t$.

Consider the sequence

$y_i = x_{i+p+q} - x_i, \quad i = 0, \dots, n - p - q.$

We claim that at least one of the $y_i$’s equals zero.

Each $y_i$ is of the form $u p - v q$, where $u + v = p + q$; therefore

$y_i = (u + v) p - v (p + q) = (p - v)(p + q)$

is always divisible by $p + q$. Moreover,

$y_{i+1} - y_i = (x_{i+p+q+1} - x_{i+p+q}) - (x_{i+1} - x_i)$

is $0$ or $\pm(p + q)$. We conclude that if no $y_i$ is $0$, then all $y_i$’s are of the same sign. But this contradicts

$y_0 + y_{p+q} + \cdots + y_{n - p - q} = x_n - x_0 = 0.$

Consequently, some $y_i$ is zero, as claimed.

Second solution.

As before, assume $(p, q) = 1$. Define a sequence of points $A_i(y_i, z_i)$ ($i = 0, 1, \dots, n$) in $\mathbb{N}_0^2$ inductively as follows:

Set $A_0 = (0, 0)$ and define

\begin{cases} (y_i, z_i + 1) & \text{if } x_{i+1} = x_i + p,\ (y_i + 1, z_i) & \text{if } x_{i+1} = x_i - q. \end{cases}$$The points $A_i$ form a trajectory $L$ in $\mathbb{N}0^2$ continuously moving upwards and rightwards by steps of length $1$. Clearly,$$x_i = p z_i - q y_i \quad \text{for all } i.$$Since $x_n = 0$, it follows that $(z_n, y_n) = (k q, k p)$, $k \in \mathbb{N}$. Since $y_n + z_n = n > p + q$, it follows that $k > 1$. We observe that $x_i = x_j$ if and only if $A_i A_j \parallel A_0 A_n$. We shall show that such $i, j$ with $i < j$ and $(i, j) \neq (0, n)$ must exist. If $L$ meets $A_0 A_n$ in an interior point, then our statement trivially holds. From now on assume the opposite. Let $P{ij}$ be the rectangle with sides parallel to the coordinate axes and vertices at $(i p, j q)$ and $((i + 1) p, (j + 1) q)$. Let $L_{ij}$ be the part of the trajectory $L$ lying inside $P_{ij}$. We may assume w.l.o.g. that the endpoints of $L_{00}$ lie on the vertical sides of $P_{00}$. Then there obviously exists $d \in {1, \dots, k-1}$ such that the endpoints of $L_{dd}$ lie on the horizontal sides of $P_{dd}$. Consider the translate $L'{dd}$ of $L{dd}$ by the vector $-d(p, q)$. The endpoints of $L'{dd}$ lie on the vertical sides of $P{00}$. Hence $L_{00}$ and $L'_{dd}$ have some point $X \neq A_0$ in common. The translate $Y$ of point $X$ by the vector $d(p, q)$ belongs to $L$ and satisfies $XY \parallel A_0 A_n$.