The original problem:
You have $2019$ $+1$s and $-1$s, find the number of ways to arrange them, such that all subsequences of even length have a sum between $-2$ and $2$.
The answer is $2 f_{2022}\times 2^{1011} $, where $f$ is the fibonacci sequence.
I'm looking into extending the problem into 2D matrices. That is,
Given a $n\times m$ matrix of $1$ and $-1$, find the number of ways to arrange them, such that all submatrices (that is $a_{i,j},l_1\le i \le r_1, l_2 \le j \le r_2$. have a sum between $-2$ and $2$
I'm still trying to code up a solution to find the number. The growth is pretty quick though.
I also came up with a problem similar in description but (I believe) not similar at all:
Given a $n\times m$ matrix of $1$ and $-1$, find the largest possible submatrix that have a sum between $-2$ and $2$ among all arrangements.
