Team Selection Test Selection Test

Solution (By Adam Hesterberg). Note that $x_n \le \max\{x_{n-1}, \dots, x_{n-n_0}\}$, so $\{x_n\}$ is a bounded sequence. Let $X$ be the largest integer that occurs infinitely often in the sequence $\{x_n\}$, and let $N$ be an integer such that for all $n > N$, $x_n \le X$. We now have a lemma.

Lemma 1. Let $m$ be a positive integer of the form $m = c_1d_1 + \dots + c_kd_k$, with $c_i$ non-negative integers. If $n > N + n_0 + m$ and $x_n = X$, then $x_{n-m} = X$.

Proof. Suppose we are given $n' > N + n_0$ with $x_{n'} = X$. Then, $x_{n'-d_i} \le X$, implying that
$$X = x_{n'} \le \frac{x_{n'-d_1} + \dots + x_{n'-d_k}}{k} \le X.$$
Equality must then hold in each step of the iterated inequality above, hence $x_{n'-d_i} = X$ for each $i$. We begin by setting $n' = n$ and apply this reasoning repeatedly, choosing $i$ at each step to decrease $n'$ to $n-m$. At each step, we change $n'$ to $n'-d_i$ while maintaining $x_{n'} = X$, allowing us to conclude that $x_{n-m} = X$. $\square$

Now, let $M$ be an integer such that for all $m > M$ there exist non-negative integers $c_1, c_2, \dots, c_k$ such that $m = c_1d_1 + c_2d_2 + \dots + c_kd_k$. Such an $M$ exists because $\gcd(d_1, \dots, d_k) = 1$. Because $X$ occurs infinitely often in $\{x_n\}$, we may find some $n > M + N + 2n_0$ for which $x_n = X$. By our choice of $M$, each $m \in \{M+1, M+2, \dots, M+n_0\}$ is the non-negative linear combination of the $d_i$. Further, we have $n > N + n_0 + m$, so by Lemma 1 we conclude $x_{n-m} = X$ for $M+1 \le m \le M+n_0$. This shows that $n_0$ consecutive terms of the sequence are equal, so the sequence is constant thereafter.