## Sunday, February 2, 2014

### 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)$