OME 1988 Problem 1

A sequence of integers $(x_n)_{n=1}^{\infty}$ satisfies $x_1 = 1$ and $x_n < x_{n+1} \le 2n$ for all $n$ . Show that for every positive integer $k$ there exist indices $r, s$ such that $x_r-x_s = k$ .