Random walk sequences

Let $n$ be a natural number. Suppose $a_1, a_2, \dots$ are sequences of +1s and -1s. Also define $s_k = a_1 + a_2 + \dots + a_k$, and define $s_0 = 0$. Such sequence is called "complete" if for each $i \in {0, \dots, n-1}$ there exists $k$ such that $s_k \equiv i \mod n$.
What is the largest number $S$ such that the following statement is true: For every complete sequence, there exists $j,k \geq 0$ such that $|s_j - s_k| = S$.

Answer:

$n-1$

We can construct $a_i$ as follows: $n-1$ +1s, followed by $n-1$ -1s, and followed by $n-1$ +1s again, alternatingly. It's easy to see that this sequence is complete. Moreover, the sum of any contiguous block ranges from $-(n-1)$ to $(n-1)$. So clearly for this particular sequence, $S \leq n-1$ fulfills the statement, and $S > n-1$ is not satisfied by this sequence.

Now we have to prove that for $S=n-1$ and any given complete sequence, the problem statement is fulfilled.

First Solution

The sequence is infinite, but suppose we can truncate it to the smallest sequence so that it's still complete. In other words, suppose the sequence $a_1, \dots, a_N$ is complete but $a_1, \dots, a_{N-1}$ is not. Let $s_N = x$. Because $N$ is the smallest index such that it's still complete, that means $s_i \equiv x \mod n$ does not happen before $N$. Consider $a_N$. It can be either +1 or -1. Suppose it's +1 (the case of -1 is similar). So that means $s_{N-1} = x-1$.

Let $p$ be the an index such that $s_p \equiv x+1 \mod n$. We know $p$ exists because the sequence is still complete. Also that $p < N-1$. That means $s_{N-1} - s_p \equiv (x-1) - (x+1) \equiv -2 \mod n$. But from $i = p$ to $i = N-1$ we can't have $s_i = x$, so that means $s_{N-1} - s_p = tn - 2$ for some $t > 0$. This means that $s_N - s_p = tn-1$.

But if $t > 1$, then we must have some $r$ such that $p < r < N$ and $s_N - s_r = n, s_r - s_p = (t-1)n-1$. But this yields a contradiction, because then $s_r \equiv s_N \equiv x \mod n$ and thus $a_1, \dot, a_r$ is complete, violating our condition that $N$ is the smallest complete sequence. Thus we must have that $t=1$ and consequently $s_N - s_p = n-1$

Second Solution

Suppose that there is no contiguous block whose sum is $\pm(n-1)$. Each contiguous block must have sum of at most $(n-2)$ and at least $-(n-2)$. Now, if there is $k$ such that $s_k = n-1$ then we are done, because it would imply a contiguous block from $0$ to $k$ with sum $n-1$. So let $x$ be the maximum value of $s_i$, where $x \leq n-2$. Likewise, let $y$ be the minimum value of $s_i$ where $y \geq -(n-2)$.

Because the sequence is complete, then we must have that $x-y \geq n-1$, otherwise some values won't be "reached" by $s_i$ at all. But this means that there is a contiguous block from the maximum to the minimum or vice versa, and their sum is $\pm(n-1)$