IMO 1996 · Problem 6

Let \(p,q,n\) be three positive integers with \(p+q<n\). Let \((x_0,x_1,\ldots,x_n)\) be an \((n+1)\)-tuple of integers satisfying the following conditions:

(a) \(x_0=x_n=0\).

(b) 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 exist indices \(i<j\) with \((i,j)\ne(0,n)\), such that \(x_i=x_j\).

Official text of the problem. Official problem paper (PDF)

Solution

Put \(m=p+q\), so \(0<m<n\), and define \[ a_k=x_k-x_{k-1}\qquad(1\le k\le n). \] Then each \(a_k\) is either \(p\) or \(-q\), and \[ \sum_{k=1}^{n}a_k=x_n-x_0=0. \] Extend the sequence \(a_k\) periodically by \(a_{k+n}=a_k\).

For \(r=0,1,\ldots,n-1\), consider the sum of \(m\) consecutive terms \[ S_r=\sum_{k=1}^{m}a_{r+k}. \] We establish three properties.

First, every \(S_r\) is a multiple of \(m\). Indeed, if its block contains \(u\) terms equal to \(p\), then \[ S_r=up-(m-u)q=m(u-q). \]

Second, for \(0\le r\le n-2\), \[ S_{r+1}-S_r=a_{r+m+1}-a_{r+1}\in\{-m,0,m\}. \]

Third, each of \(a_1,\ldots,a_n\) occurs exactly \(m\) times among the \(n\) cyclic blocks, so \[ \sum_{r=0}^{n-1}S_r =m\sum_{k=1}^{n}a_k=0. \]

These properties imply that some \(S_r\) is zero. Otherwise, their zero total would force both positive and negative values. Somewhere in the list \(S_0,\ldots,S_{n-1}\), two adjacent values would therefore have opposite signs. As nonzero multiples of \(m\), they would differ by at least \(2m\), contradicting the second property.

Choose \(r\) with \(S_r=0\). If \(r+m\le n\), then \[ 0=S_r=x_{r+m}-x_r. \] Thus \(i=r\), \(j=r+m\) give the required equality; their difference is \(m<n\), so they cannot be \(0,n\).

If \(r+m>n\), periodicity gives \[ 0=S_r=(x_n-x_r)+(x_{r+m-n}-x_0) =x_{r+m-n}-x_r. \] Here \[ 0<r+m-n<r<n, \] because \(m<n\). Hence \(i=r+m-n\), \(j=r\) give the required equality in this case as well. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).