Problem 1425

1. **Define the sequence and the set $A$**:
- We are given a sequence of integers $(x_n)_{n=1}^{\infty}$ such that $x_1 = 1$ and $x_n < x_{n+1} \le 2n$ for all $n$.
- We need to show that for every positive integer $k$, there exist indices $r$ and $s$ such that $x_r - x_s = k$.

2. **Construct the set $A$**:
- Consider the set $A = \{1, 2, \ldots, 2k\}$.
- We will divide this set into $k$ disjoint subsets:
$$\{1, k+1\}, \{2, k+2\}, \ldots, \{k, 2k\}.$$

3. Apply the given inequality:
- According to the given inequality $x_n < x_{n+1} \le 2n$, the first $k+1$ terms of the sequence $x_1, x_2, \ldots, x_{k+1}$ must all be elements of the set $A$.

4. Use the Pigeonhole Principle:
- Since there are $k+1$ numbers $x_1, x_2, \ldots, x_{k+1}$ and only $k$ disjoint subsets in $A$, by the Pigeonhole Principle, at least one of these subsets must contain at least two of the numbers from the sequence.
- Let $i \in \{1, 2, \ldots, k\}$ be such that two different integers from the sequence belong to the set $\{i, k+i\}$.

5. Find the difference:
- If $x_r$ and $x_s$ are the two integers from the sequence that belong to the set $\{i, k+i\}$, then their difference is:
$$x_r - x_s = k \quad \text{or} \quad x_s - x_r = k.$$

6. Conclusion:
- Therefore, for every positive integer $k$, there exist indices $r$ and $s$ such that $x_r - x_s = k$.

$\blacksquare$