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.
by
Sreejato Bhattacharya