Problem 2117

Solution:

Suppose the claim were not satisfied. Then there exists an index $N>10^{100}$ such that for all $i \geq N$ either $a_{i} \leq i-d$ or $a_{i} \geq i+d$ holds. In the first case, since $i \geq N>10^{100}$, by the second assumption on the sequence we also have
$$a_{i+1} \leq a_{i}+2 d \leq i-d+2 d=(i+1)+(d-1)$$
so $a_{i+1} \leq(i+1)-d$ must hold. By induction it follows that $a_{i} \leq j-d$ for all $j \geq i$.
We have thus shown:
(A) Either $a_{i} \geq i+d$ holds for all $i \geq N$, or
(B) there exists an $M \geq N$ such that $a_{i} \leq i-d$ holds for all $i \geq M$.
Let us first assume that (A) is satisfied. The numbers $1, \ldots, N$ must, by the first assumption on the sequence, each occur once in the sequence. However, we have $a_{i} \geq i+d>i \geq N$ for all $i \geq N$, that is, there are only the $N-1$ sequence terms $a_{1}, \ldots, a_{N-1}$ that can take one of these values. By the pigeonhole principle this yields a contradiction.
Now let us assume that (B) is satisfied. Let $k=\max \left\{M, a_{1}, \ldots, a_{M}\right\}$. Then the $k$ sequence terms $a_{1}, \ldots, a_{k}$ are all less than $k$, since for $i=1, \ldots M-1$ we have $a_{i} \leq \max \left\{a_{1}, \ldots, a_{M-1}\right\} \leq k$ and for $i=M, \ldots, k$ we have $a_{i} \leq i-d<i \leq k$. These $k$ numbers thus all lie in the set $\{1,2, \ldots, k-1\}$. By the pigeonhole principle there therefore exist two indices $1 \leq i<j \leq k$ with $a_{i}=a_{j}$, which contradicts the first assumption on the sequence.
Since we have obtained a contradiction in every case, the claim holds.