United States — Team Selection Test

The statement is true for all $n \ge 4$ but not for $n = 2$ or $n = 3$. In those two cases, the sequences $(1, 2)$ and $(2, 1, 2)$ provide counterexamples.

Now, let $(a_1, \dots, a_n)$ be any sequence of positive integers, and let $s_k = a_1 + \dots + a_k - 2k$ for $k = 1, 2, \dots, n$, and define $s_0 = 0$. Let us say that a sequence is good if it satisfies the property in the problem (no block of length at least two has an integer arithmetic mean). Define $(i, j)$ to be a divisible pair if $j - i \mid s_j - s_i$. It is clear that $(a_1, \dots, a_n)$ is good if and only if there is no divisible pair $(i, j)$ such that $|j - i| \ge 2$.

We will show that $(a_1, \dots, a_n)$ is not good if $n \ge 4$. Note that $s_n = a_1 + \dots + a_n - 2n = -1$, and for each $k$, $s_{k+1} - s_k = a_{k+1} - 2 \ge -1$. We consider several possible values of $s_2$.

* Suppose $s_2 \le -2$. Since $s_1 \ge s_0 - 1 = -1$ and $s_2 \ge s_1 - 1$, it follows that $s_1 = -1$. Then $n-1 \mid s_n - s_1$.

* Suppose $s_2 = -1$. Then $n-2 \mid s_n - s_2$.

* Suppose $s_2 = 0$. Then $2-0 \mid s_2 - s_0$.

* Suppose $s_2 \ge 1$. Since $s_n = -1$, and $s_{k+1}$ can be no smaller than $s_k$, there must be some $i$ between 2 and $n$ such that $s_i = 0$. Then $i-0 \mid s_i - s_0$.

We have thus shown that there is at least one divisible pair among the pairs $(1, n)$, $(2, n)$, $(0, 2)$, and $(0, i)$, for some $2 < i < n$. Note that if $n \ge 4$, the two numbers in each of those pairs must differ by at least two. Thus, $(a_1, \dots, a_n)$ is not good when $n \ge 4$, finishing the proof.