# Balanced String

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...