Let $\{x_n\}$ be a sequence of natural numbers such that \[(a) 1 = x_1 < x_2 < x_3 < \ldots; \quad (b) x_{2n+1} \leq 2n \quad \forall n.\] Prove that, for every natural number $k$, there exist terms $x_r$ and $x_s$ such that $x_r - x_s = k.$
Source: IMO 1980 Austria-Poland, problem 2
Tags: algebra, Sequence, equation, IMO Shortlist
Let $\{x_n\}$ be a sequence of natural numbers such that \[(a) 1 = x_1 < x_2 < x_3 < \ldots; \quad (b) x_{2n+1} \leq 2n \quad \forall n.\] Prove that, for every natural number $k$, there exist terms $x_r$ and $x_s$ such that $x_r - x_s = k.$