Balanced String

Discrete Mathematics Level 5

Let \(S= \{1, -1\}\). A sequence \((a_1, a_2, \cdots , a_n)\) is called balanced if the following conditions hold:

  • \(a_i \in S\) for all \(1 \leq i \leq n\)
  • Define \(S_i= a_1 + a_2 + \cdots + a_i\). Then, \(|S_i| \leq 2\) for all \( 1 \leq i \leq n\).
  • Moreover, for all \(1 \leq i < j \leq n\), we have \(|S_i-S_j| \leq 2\).

Find the number of balanced sequences of length \(2016\) (the number of balanced sequences with \(n=2016\)). Enter the last three digits of the answer.


Problem Loading...

Note Loading...

Set Loading...